백준 2463번 비용

< 백준 2463번 비용 - 마포 코딩박 >

사용한 알고리즘: Union-Find


 문제에서 Cost(u,v) 는 최소 간선부터 제거하면서 u,v 가 다른 component 일 때 까지 제거되는 간선의 합입니다. 이때 u<v 인 모든 정점 u,v 에 대해 Cost(u,v) 들의 총 합을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (생각)
 거꾸로 생각하여 모든 정점이 분리되어 있고, 최대 간선부터 차례로 연결하며 해당 간선을 연결하여 같은 component 가 되는 정점 u, v 에 대해 볼 것입니다.
 문제에서 주어진 예시를 예로 들면,
 1. 초기 6개의 정점은 따로 떨어져 있고 모든 간선의 합은 45 입니다.
 2. 먼저 최대 간선인 15 를 연결하면 정점 3, 6은 하나의 component가 되고, 따라서 Cost(3,6) = 45 입니다. 이후 남은 모든 간선의 합은 30 입니다.
 3. 이 다음 최대 간선 10을 연결하면 정점 1, 2는 하나의 component가 되고 Cost(1, 2) = 30 입니다. 이후 남은 모든 간선의 합은 20 입니다.
 4. 이 다음 최대 간선 6을 연결하면 정점 1,3 / 1,6 / 2,3 / 2,6 은 하나의 component가 되고 Cost(1,3) = Cost(1,6) = Cost(2,3) = Cost(2,6) = 20 입니다. 이후 남은 모든 간선의 합은 14입니다.
 위 과정을 남은 간선이 없을때 까지 반복하면 됩니다.

(2) (코드 10~22)
 입력되는 정점 a, b 를 있는 간선의 가중치 w 를 하나의 struct로 vector에 저장합니다. 이후 가중치가 큰 간선부터 차례로 볼 것입니다.

(3) (코드 23~43, 63~75)
 최대 가중치와 그에 연결되는 정점 a,b 를 차례로 보며 다음 과정을 진행합니다.
 Union-Find 로 a,b 의 component를 확인하고, 둘이 다른 component 일 경우, 두 component에 포함된 정점 수 각각 찾습니다.
 이 두 정점수를 곱해 새로 만들어지는 Cost(u,v) 개수를 찾고, 이에 남은 모든 간선의 합을 곱해 구하고자 하는 답에 추가합니다.

	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <cstring>
	using namespace std;
	typedef long long ll;
	const ll MOD = 1e9;
	const int MAX = 100000;
	int N, M;
	// A~B 의 가중치 W
	struct Edge{
	int A;
	int B;
	ll W;
	Edge():Edge(0,0,0){}
	Edge(int a1, int b1, ll w1): A(a1), B(b1), W(w1){}
	};
	vector<Edge> V;
	// 가중치 W 큰거부터
	bool cmp(const Edge &E1, const Edge &E2){
	return E1.W > E2.W;
	}
	// i 의 root
	int R[MAX+1];
	int Find(int x){
	if(R[x]<0) return x;
	return R[x] = Find(R[x]);
	}
	// R[aRoot] * R[bRoot] 의 개수 : edge(x,y) 로 만들어지는 Cost 쌍의 수
	ll Union(int x, int y){
	ll tt = 0LL;
	int xRoot = Find(x);
	int yRoot = Find(y);
	// 이미 같은 group 이면 return 0
	if(xRoot==yRoot) return tt;
	// R[xRoot] : -( xRoot 를 root 로 하는 정점의 수 )
	tt = (ll)R[xRoot];
	tt *= (ll)R[yRoot];
	// R[yRoot] 에 xRoot를 root 로 하는 정점 수 추가
	R[yRoot] += R[xRoot];
	R[xRoot] = yRoot;
	return tt;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	// 초기 root 값들 -1
	memset(R, -1, sizeof(R));
	// 곱해줄 무게
	ll temp = 0LL;
	// 정답
	ll ans = 0LL;
	cin >> N >> M;
	for(int i=0; i<M; ++i){
	int a, b;
	ll w;
	cin >> a >> b >> w;
	// 남은 모든 간선들의 합
	temp+=w;
	//temp%=MOD; <- 이거 해주면 74번째 줄에서 음수 나올 수 있습니다!!!!!!!!!!!!!!
	V.push_back(Edge(a,b,w));
	}
	// 가중치 큰 거 먼저.
	sort(V.begin(), V.end(), cmp);
	for(auto curr: V){
	int a = curr.A;
	int b = curr.B;
	// 해당 가중치가 만드는 개수
	ll num = Union(a,b);
	// num * 해당 가중치 까지 빼야됐던 작은 무게들
	if(num!=0LL){
	ans+=temp*num;
	ans%=MOD;
	}
	temp-=curr.W;
	}
	cout << ans%MOD << '\n';
	return 0;
	}

view raw BOJ 2463.cpp hosted with ❤ by GitHub