제출 #1170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170		kriii	비용 (KOI11_cost)	C++98	6 / 24	64 ms	3624 KiB

cost

#include <stdio.h>
#include <algorithm>

struct edge{int x,y; long long c;} E[100010];
bool cmp(const edge& a, const edge& b){return a.c > b.c;}

const long long mod = 1000000009;
int N,M,P[100010]; long long C[100010],CON,ANS;

int find(int x){return P[x] = (x == P[x]) ? x : find(P[x]);}

int main()
{
	int i,x,y;

	scanf ("%d %d",&N,&M);
	for (i=0;i<M;i++) scanf ("%d %d %lld",&E[i].x,&E[i].y,&E[i].c);
	std::sort(E,E+M,cmp);

	for (i=1;i<=N;i++){
		P[i] = i;
		C[i] = 1;
	}
	for (i=0;i<M;i++){
		x = find(E[i].x);
		y = find(E[i].y);

		if (x != y){
			P[y] = x;
			CON = (CON + C[x] * C[y]) % mod;
			C[x] += C[y];
		}

		ANS = (ANS + CON * E[i].c) % mod;
	}

	printf ("%lld",ANS);

	return 0;
}

• Subtask 1: 4.8 / 4.8
• Subtask 2: 1.2 / 7.2
• Subtask 3: 0 / 12