hdu1863 畅通工程 Kruskal/Prim

题目链接:

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

题意:

题解:

Kruskal是按照边权排序，每次选择一条最小的边，判断这条边的两个端点是否在同一个集合，用并查集维护
Prim是随便选择一个点作为当前集合，找到与这个集合相连的边中最短的那条，用优先队列取出最短的，如果另一个端点不在当前集合，就加进来，并且把与这个点相连的所有边加到优先队列里

代码:

Kruskal：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 100+10;
17 
18 int N,M,fa[maxn];
19 ll ans;
20 
21 struct node{
22     int u,v,w;
23     bool operator<(const node& rhs)const{
24         return w < rhs.w;
25     }
26 }E[maxn];
27 
28 int find(int x){
29     return fa[x]==x ? x : fa[x]=find(fa[x]);
30 }
31 
32 void Union(int x,int y){
33     int p1 = find(x), p2 = find(y);
34     if(p1 == p2) return;
35     fa[p1] = p2;
36 }
37 
38 bool same(int x,int y){
39     return find(x)==find(y);
40 }
41 
42 void kruskal(){
43     sort(E,E+M);
44     for(int i=0; i<M; i++){
45         int u = E[i].u, v = E[i].v, w = E[i].w;
46         if(same(u,v)) continue;
47         Union(u,v);
48         ans += w;
49     }
50 }
51 
52 int main(){
53     while(scanf("%d%d",&M,&N)==2){
54         if(M==0) break;
55         ans = 0;
56         for(int i=0; i<maxn; i++) fa[i] = i;
57         for(int i=0; i<M; i++){
58             int u,v,w; scanf("%d%d%d",&u,&v,&w);
59             E[i].u = u, E[i].v = v, E[i].w = w;
60         }
61 
62         kruskal();
63 
64         for(int i=1; i<=N; i++)
65             if(same(1,i) == 0)
66                 ans = -1;
67         if(ans == -1)
68             cout << "?
";
69         else
70             cout << ans << endl;
71     }   
72 
73     return 0;
74 }

Prim：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 100+10;
17 
18 struct node{
19     int to,cost;
20     node(int to=0,int cost=0) : to(to),cost(cost) {}
21     bool operator<(const node& rhs)const{
22         return cost > rhs.cost;
23     }
24 };
25 
26 priority_queue<node> que;
27 std::vector<node> G[maxn];
28 
29 int N,M;
30 bool vis[maxn];
31 
32 ll prim(){
33     ll res = 0;
34     vis[1] = 1;
35     for(int i=0; i<(int)G[1].size(); i++)
36         que.push(node(G[1][i]));
37     while(!que.empty()){
38         node e = que.top(); que.pop();
39         if(vis[e.to]) continue;
40         vis[e.to] = 1;
41         res += e.cost;
42         for(int i=0; i<(int)G[e.to].size(); i++)
43             que.push(G[e.to][i]);
44     }
45     return res;
46 }
47 
48 int main(){
49     while(scanf("%d%d",&M,&N) == 2){
50         if(M == 0) break;
51         for(int i=0; i<=N; i++) G[i].clear();
52         while(que.size()) que.pop();
53         MS(vis);
54         for(int i=1; i<=M; i++){
55             int u,v,w;scanf("%d%d%d",&u,&v,&w);
56             G[u].push_back(node(v,w));
57             G[v].push_back(node(u,w));
58         }
59 
60         ll res = prim();
61 
62         for(int i=1; i<=N; i++)
63             if(vis[i] == 0)
64                 res = -1;
65         if(res == -1)
66             printf("?
");
67         else
68             printf("%I64d
",res);
69 
70     }
71 
72     return 0;
73 }