[BOJ 24977] Visits

https://www.acmicpc.net/problem/24977

24977번: Visits

 

- 문제 요약

 

베시의 N명의(2<=N<=10^5) 소 친구들은 (1... N 번호가 붙은) 각자 자기 농장을 소유하고 있어요.

또한, 각각의 1<=i<=N, buddy a_i(a_i != i)를 방문하고 싶습니다.

순열 (p_1,p_2,...,p_N)이 1일 때... N, 방문은 다음과 같이 이루어집니다.

1부터 N까지 각 i에 대해:
buddy a_{p_i}가 이미 그녀의 농장을 떠난 경우, buddy p_i는 그녀 자신의 농장에 남아 있습니다.
그렇지 않으면 버디 p_i는 버디 a_{p_i}의 농장을 방문하기 위해 그녀의 농장을 떠난다.
이 방문은 즐거운 "moo"가 v_{p_i}번(0<=v_{p_i}<=10^9) 발음되는 결과를 낳는다.
모든 방문 후 가능한 모든 순열 p에 걸쳐 가능한 최대 moo의 수를 계산합니다.

 

 

- 알고리즘 정리

 

크루스칼 알고리즘으로 쭉 돌려주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
struct st{
	vector<int>e;
	void init(int N){
		e=vector<int>(N,-1); 
	}
	int get(int x){
		return e[x]<0?x:e[x]=get(e[x]);
	}
	bool unite(int x,int y){
		x=get(x),y=get(y);
		if(x==y){
			return false;
		}
		if(e[x]>e[y]){
			swap(x,y);
		}
		e[x]+=e[y];
		e[y]=x;
		return true;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll N,result=0;
	vector<tuple<int,int,int>>vec;
	cin>>N;
	for(int i=1;i<=N;i++){
		int a,b;
		cin >> a >> b;
		vec.push_back({b,i,a});
	}
	sort(vec.rbegin(),vec.rend());
	st w;
	w.init(N+1);
	for(auto [i,x,y]:vec){
		if(w.unite(x,y)){
			result+=i;
		}
	}
	cout<<result;
}

코드 제출 결과

GCC 버전 때문에.... tuple 부분에서 에러가 떠서.....내가... 뭘 잘못했나.... 내 눈이 잘못된 건가.....