HDU 1863 畅通工程

Portal：http://acm.hdu.edu.cn/showproblem.php?pid=1863

依然最小生成树+并查集

因为不保证所有村庄在一个强连通分量里，所以用并查集要判断能否“畅通”

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<vector>
 8 using namespace std;
 9 #define FOR(i,j,k) for(int i=j;i<=k;i++)
10 #define FORD(i,j,k) for(int i=j;i>=k;i--)
11 #define LL long long
12 #define maxnn 10110
13 #define maxn 110
14 struct edge{int u,v,cost;};
15 edge bb[maxnn];
16 int father[maxn],val[maxn];
17 int n,x,y,z,k,ans;
18 void setinit()
19 {
20     FOR(i,1,n)
21     {father[i]=i; val[i]=1;}
22 }
23 int setfind(int x)
24 {
25     int fa=father[x];
26     if(fa==x) return x;
27     else return father[x]=setfind(fa);
28 }
29 bool setunion(int xx,int yy)
30 {
31     int XX=setfind(xx);
32     int YY=setfind(yy);
33     if(XX==YY) return false;
34     if(val[XX]>val[YY]) father[YY]=XX;
35     else father[XX]=YY;
36     if(val[XX]=val[YY]) val[XX]++;
37     return true;
38 }
39 bool cmp1(edge a,edge b)
40 {
41     return a.cost<b.cost;
42 }
43 void kruskal()
44 {
45     sort(bb+1,bb+k+1,cmp1);
46     FOR(i,1,k)
47     if(setunion(bb[i].u,bb[i].v)) ans+=bb[i].cost;
48 }
49 bool setcheck()
50 {
51     FOR(i,1,n-1)
52     if(setfind(i)!=setfind(i+1)) return false;
53     return true;
54 }
55 int main()
56 {
57 for(cin>>k>>n;k!=0;cin>>k>>n)
58 {
59     FOR(i,1,k)    
60     {
61         cin>>x>>y>>z;
62         bb[i].u=x;
63         bb[i].v=y;
64         bb[i].cost=z;
65     }
66     setinit();
67     ans=0;
68     kruskal();
69     if(setcheck())cout<<ans<<endl;else cout<<'?'<<endl;
70 }
71 return 0;
72 }

乱搞出奇迹

哈哈哈哈0msAC，计划通