[정올 2467] 비용

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1728&sca=99&sfl=wr_hit&stx=2467 

JUNGOL

/*
비용
union find
가장 큰 비용을 가지는 w는, 해당 시작점 s와 끝점 e의 비용을 구할 때만 쓰이고 나머지 경로에서는 안 쓰인다.
즉 가장 큰 비용 w는 Cost(s,e) 딱 한 번에서만 쓰인다.
가장 큰 w가 쓰인다는 것은 Cost가 모든 w의 합이라는 뜻이다.
가장 큰 w를 쓰고 나면, 이제 w는 짤릴 일이 없으므로 w로 연결된 s, e를 하나의 점으로 여길 수 있다.
그렇다면, s,e가 아닌 점 a에 대해 Cost(a,s) == Cost(a,e)가 된다. 즉 각개격파가 되는 것이며 
따라서 합쳐진 그룹의 대표 Cost(a,s)만 구하고 s가 포함된 그룹의 개수만큼 곱해주면 여러 경우의 수를 한 번에 구할 수 있다.
*/
#include <stdio.h>

typedef long long LL;
const int LM = 100010;		//총 데이터 10만
const int MOD = (int)1e9;	//합이 10^9보다 크다면 나머지만 구해야 하므로

//G는 idx인 점이 어느 곳과 연결되어 있는지를 알려줌, cnt는 해당 점과 연결된 노드들의 수(하나로 봐야할 노드)
int N, M, G[LM], cnt[LM];
LL sum, ans; //현재 최대 비용과, 답(10^9의 나머지)
struct Data {
	int s, e, w; //시작점, 끝점, 그 사이의 비용
	//bool operator<(const Data&r)const {
	//	return w > r.w;
	//}
}A[LM], trr[LM];

bool comp(Data&a, Data&b) {
	return a.w > b.w;
}

void input() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; ++i) {
		scanf("%d%d%d", &A[i].s, &A[i].e, &A[i].w);
		sum += A[i].w; //***현재 모든 구간이 없을 때의 총 비용을 미리 계산한다.
	}
	for (int i = 1; i <= N; ++i) {//초기화
		G[i] = i; //초기에 각 그룹은 자기 자신만 있는 단독그룹이다.
		cnt[i] = 1;//각 그룹의 점 수는 당연히 1
	}
}

void mergeSort(Data*arr, int s, int e) {
	if (s >= e) return;
	int m = (s + e) / 2, i = s, j = m + 1, k = s;
	mergeSort(arr, s, m);
	mergeSort(arr, m + 1, e);
	for (; k <= e; ++k) {
		if (i > m) trr[k] = arr[j++];
		else if (j > e) trr[k] = arr[i++];
		else if (comp(arr[i], arr[j]))
			trr[k] = arr[i++];
		//else if (arr[i]<arr[j]) trr[k] = arr[i++];
		else trr[k] = arr[j++];
	}
	for (i = s; i <= e; ++i) arr[i] = trr[i];
}

int Find(int r) {//점 r이 어느 그룹을 따르는지 리턴하고, 따르는 점들이 전부 root를 따르도록 수정
	return G[r] = r == G[r] ? r : Find(G[r]);
}
void unionFind() { //w로 정렬된 배열을 가지고 가장 큰 w부터 줄여가며 계산한다.
	for (int i = 1; i <= M; ++i) { //가장 큰 w로 연결된 s,e부터 내려간다.
		int s = Find(A[i].s), e = Find(A[i].e); //w로 연결된 s와 e의 그룹을 구함
		if (s != e) { //그룹이 다르면
			//현재 w가 현재기준 max값이므로, Cost(s,e)는 모든 w를 자른 비용이다.
			//s에 속한 그룹 노드중 하나 고르는 방법(sC1) * eC1(e에 속한 그룹) * 모든 w를 자른 비용
			ans = (ans + sum * cnt[s] % MOD*cnt[e]) % MOD;
			G[e] = s; //s와 e는 이제 같은 그룹
			cnt[s] += cnt[e]; //같은 그룹이 되었으므로 두 그룹의 점 개수 합침
		}
		sum -= A[i].w;//가장 큰 w를 전체w합에서 제거함
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	input();
	mergeSort(A, 1, M); //w의 크기에 따라 소팅한다.
	unionFind();
	printf("%lld\n", ans);
	return 0;
}