题意是求将所有点联通所花费的最小金额,如不能完全联通,输出 -1
直接Kruskal,本题带来的一点教训是 rank 是algorithm头文件里的,直接做变量名会导致编译错误。没查到 rank 的具体用途......
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> /*rank 是algorithm里的*/ 4 using namespace std; 5 int father[100005],r[100005]; 6 int n,m,k,ans; 7 struct edg 8 { 9 int from,to,money; 10 }e[100005]; 11 int fd(int x) 12 { 13 if(x==father[x]) return x; 14 return fd(father[x]); 15 } 16 void makeset(int x) 17 { 18 for(int i = 1; i <= x;i++) 19 { 20 father[i] = i; 21 r[i] = 1; 22 } 23 } 24 void uon(int x,int y) 25 { 26 x = fd(x); 27 y = fd(y); 28 if(x!=y) 29 { 30 if(r[x] >= r[y]) 31 { 32 father[y] = x; 33 r[x] += r[y]; 34 r[y] = 0; 35 } 36 else 37 { 38 father[x] = y; 39 r[y] += r[x]; 40 r[x] = 0; 41 } 42 } 43 } 44 bool cmp(edg x,edg y) 45 { 46 return x.money < y.money; 47 } 48 int main() 49 { 50 int t,p,len; 51 scanf("%d",&t); 52 while(t--) 53 { 54 scanf("%d%d%d",&n,&m,&k); 55 makeset(n); 56 ans = 0; 57 len = 0; 58 for(int i = 1; i <= m; i++) 59 scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].money); 60 for(int i = 1; i <= k; i++) 61 { 62 scanf("%d",&p); 63 int a,b(0); 64 for(int u = 0; u < p ;u++) 65 { 66 scanf("%d",&a); 67 if(u&&b) uon(a,b); 68 b = a; 69 } 70 } 71 sort(e+1,e+1+m,cmp); 72 for(int i = 0; i < m; i++) 73 if(fd(e[i].from)!=fd(e[i].to)) 74 { 75 uon(e[i].from,e[i].to); 76 ans += e[i].money; 77 } 78 for(int i = 1; i <= n; i++) 79 if(r[i] > 0) len++; //检查所有点是否只有一个根,即是否存在未连在树上的点 80 if(len == 1) printf("%d\n",ans); 81 else printf("-1\n"); 82 } 83 return 0; 84 }