#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 = 1000000000;
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3624 KB |
Output is correct |
2 |
Correct |
0 ms |
3624 KB |
Output is correct |
3 |
Correct |
0 ms |
3624 KB |
Output is correct |
4 |
Correct |
0 ms |
3624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3624 KB |
Output is correct |
2 |
Correct |
0 ms |
3624 KB |
Output is correct |
3 |
Correct |
0 ms |
3624 KB |
Output is correct |
4 |
Correct |
0 ms |
3624 KB |
Output is correct |
5 |
Correct |
2 ms |
3624 KB |
Output is correct |
6 |
Correct |
3 ms |
3624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
3624 KB |
Output is correct |
2 |
Correct |
26 ms |
3624 KB |
Output is correct |
3 |
Correct |
58 ms |
3624 KB |
Output is correct |
4 |
Correct |
11 ms |
3624 KB |
Output is correct |
5 |
Correct |
60 ms |
3624 KB |
Output is correct |
6 |
Correct |
25 ms |
3624 KB |
Output is correct |
7 |
Correct |
56 ms |
3624 KB |
Output is correct |
8 |
Correct |
61 ms |
3624 KB |
Output is correct |
9 |
Correct |
54 ms |
3624 KB |
Output is correct |
10 |
Correct |
58 ms |
3624 KB |
Output is correct |