hdu1863 畅通工程 Kruskal/Prim

2019-11-06 07:17:25

字体：大中小

来源：转载

供稿：网友

题目链接:

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

题意:

题解:

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

代码:

Kruskal：

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//////////////////////////////////////////////////////////////////////////const int maxn = 100+10;int N,M,fa[maxn];ll ans;struct node{ int u,v,w; bool Operator<(const node& rhs)const{ return w < rhs.w; }}E[maxn];int find(int x){ return fa[x]==x ? x : fa[x]=find(fa[x]);}void Union(int x,int y){ int p1 = find(x), p2 = find(y); if(p1 == p2) return; fa[p1] = p2;}bool same(int x,int y){ return find(x)==find(y);}void kruskal(){ sort(E,E+M); for(int i=0; i<M; i++){ int u = E[i].u, v = E[i].v, w = E[i].w; if(same(u,v)) continue; Union(u,v); ans += w; }}int main(){ while(scanf("%d%d",&M,&N)==2){ if(M==0) break; ans = 0; for(int i=0; i<maxn; i++) fa[i] = i; for(int i=0; i<M; i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); E[i].u = u, E[i].v = v, E[i].w = w; } kruskal(); for(int i=1; i<=N; i++) if(same(1,i) == 0) ans = -1; if(ans == -1) cout << "?/n"; else cout << ans << endl; } return 0;}

Prim：

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//////////////////////////////////////////////////////////////////////////const int maxn = 100+10;struct node{ int to,cost; node(int to=0,int cost=0) : to(to),cost(cost) {} bool operator<(const node& rhs)const{ return cost > rhs.cost; }};priority_queue<node> que;std::vector<node> G[maxn];int N,M;bool vis[maxn];ll prim(){ ll res = 0; vis[1] = 1; for(int i=0; i<(int)G[1].size(); i++) que.push(node(G[1][i])); while(!que.empty()){ node e = que.top(); que.pop(); if(vis[e.to]) continue; vis[e.to] = 1; res += e.cost; for(int i=0; i<(int)G[e.to].size(); i++) que.push(G[e.to][i]); } return res;}int main(){ while(scanf("%d%d",&M,&N) == 2){ if(M == 0) break; for(int i=0; i<=N; i++) G[i].clear(); while(que.size()) que.pop(); MS(vis); for(int i=1; i<=M; i++){ int u,v,w;scanf("%d%d%d",&u,&v,&w); G[u].push_back(node(v,w)); G[v].push_back(node(u,w)); } ll res = prim(); for(int i=1; i<=N; i++) if(vis[i] == 0) res = -1; if(res == -1) printf("?/n"); else printf("%I64d/n",res); } return 0;}

上一篇：Linux--mmap实现进程间通信

下一篇：广度优先搜索BFS之二叉树的构造及遍历