#include <cstdio>
#include <algorithm>
struct data{
int x,y,w;
bool operator<(const data&r)const{
return w>r.w;
}
}path[100010];
int g[100010],cnt[100010],n;
long long int ans,w;
int seek(int nod){
if(g[nod]==nod)return nod;
return g[nod]=seek(g[nod]);
}
void merge(int a,int b){
a=seek(a);
b=seek(b);
if(a==b)
{
++n;
return;
}
ans+=w*cnt[a]*cnt[b];
g[b]=a;
cnt[a]+=cnt[b];
}
int main(){
int i,m,t;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i){
scanf("%d%d%d",&path[i].x,&path[i].y,&path[i].w);
w+=path[i].w;
}
std::sort(&path[1],&path[m+1]);
for(i=1;i<=n;++i)g[i]=i,cnt[i]=1;
for(i=1;i<n&&i<=m;++i){
merge(path[i].x,path[i].y);
w-=path[i].w;
ans%=1000000000;
}
printf("%d",ans);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3036 KB |
Output is correct |
2 |
Correct |
0 ms |
3036 KB |
Output is correct |
3 |
Correct |
0 ms |
3036 KB |
Output is correct |
4 |
Correct |
0 ms |
3036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3036 KB |
Output is correct |
2 |
Correct |
0 ms |
3036 KB |
Output is correct |
3 |
Correct |
0 ms |
3036 KB |
Output is correct |
4 |
Correct |
0 ms |
3036 KB |
Output is correct |
5 |
Correct |
0 ms |
3036 KB |
Output is correct |
6 |
Correct |
5 ms |
3036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
3036 KB |
Output is correct |
2 |
Correct |
30 ms |
3036 KB |
Output is correct |
3 |
Correct |
48 ms |
3036 KB |
Output is correct |
4 |
Correct |
0 ms |
3036 KB |
Output is correct |
5 |
Correct |
64 ms |
3036 KB |
Output is correct |
6 |
Correct |
30 ms |
3036 KB |
Output is correct |
7 |
Correct |
43 ms |
3036 KB |
Output is correct |
8 |
Correct |
64 ms |
3036 KB |
Output is correct |
9 |
Correct |
56 ms |
3036 KB |
Output is correct |
10 |
Correct |
51 ms |
3036 KB |
Output is correct |