NC25450. HRY and tree
描述
输入描述
The first line of the input file contains a positive integer T, indicating the number of test cases.
Each case has n lines. The first line is a positive integer n, indicating the number of points; the next n-1 lines each line contains three positive integers u, v, w, indicating that there is an edge between u and v, and the weight of this edge is w.
It is guaranteed that the input forms a tree.
The sum of n does not exceed 2000000.
输出描述
For each test case, output a line of a positive integer representing the sum of the weights of all paths.
示例1
输入:
2 3 1 2 1 2 3 2 4 1 2 1 1 3 2 1 4 3
输出:
5 14
C++11(clang++ 3.9) 解法, 执行用时: 1169ms, 内存消耗: 20060K, 提交时间: 2019-04-27 20:08:04
#include<bits/stdc++.h> using namespace std; typedef unsigned long long uLL; const int N=1e6+10; int T,n,fa[N],size[N]; struct edge{ int x,y,z; bool operator < (const edge &rhs) const { return z<rhs.z; } }e[N]; int getfa(int x) { return x==fa[x] ? x : fa[x]=getfa(fa[x]); } int main() { int T; cin>>T; while (T--) { scanf("%d",&n); for (int i=1;i<n;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z); sort(e+1,e+n); for (int i=1;i<=n;i++) fa[i]=i,size[i]=1; uLL ans=0; for (int i=1;i<n;i++) { int fx=getfa(e[i].x),fy=getfa(e[i].y); if (fx==fy) continue; ans+=(uLL)e[i].z*size[fx]*size[fy]; size[fx]+=size[fy]; fa[fy]=fx; } printf("%llu\n",ans); } return 0; }
C++14(g++5.4) 解法, 执行用时: 1843ms, 内存消耗: 63580K, 提交时间: 2019-05-02 16:54:24
#include<bits/stdc++.h> using namespace std; struct node{ int u,v,w; }a[1000005]; int cmp(node x,node y){ return x.w<y.w; } int fa[1000005],si[1000005]; int find(int x){ if(x!=fa[x]) return fa[x]=find(fa[x]); return fa[x]; } int main(){ int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) fa[i]=i,si[i]=1; for(int i=1;i<n;i++) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w); sort(a+1,a+n,cmp); unsigned long long ans=0; for(int i=1;i<n;i++){ int fx=find(a[i].u),fy=find(a[i].v); if(fx==fy) continue; ans+=(unsigned long long)a[i].w*si[fx]*si[fy]; si[fx]+=si[fy]; fa[fy]=fx; } printf("%llu\n",ans); } }