HDU1233 – 还是畅通工程 :?pid=1233
用了三种姿势AC这题之后, 感觉对最小生成树的理解又更深了一层. 嗯, 让你们看看我用的是哪三种姿势
方法 1 :
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int MAXN = 5000;int Father[MAXN],Ans;int N,M;int x,y;struct Node{int Now,Next,Len;}Edge[MAXN];void Initial(){M = (N * (N – 1)) / 2;Ans = 0;for(int i = 0;i < MAXN;i++)Father[i] = i;}bool Cmp(Node x,Node y){return x.Len < y.Len;}int Find(int x){return x == Father[x] ? x : Father[x] = Find(Father[x]);}int main(){while(scanf("%d",&N),N){Initial();for(int i = 1;i <= M;i++)scanf("%d%d%d",&Edge[i].Now,&Edge[i].Next,&Edge[i].Len);sort(Edge + 1,Edge + M + 1,Cmp);//注意是从1开始的编号,并按边的长度升序排序 for(int i = 1;i <= M;i++){int xx = Find(Edge[i].Now),yy = Find(Edge[i].Next);if(xx != yy)Father[xx] = yy,Ans += Edge[i].Len;}printf("%d\n",Ans);}return 0;}/*用并查集要用到结构体来储存节点和边,适合边少的情况
方法 2 :
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int MAXN = 105;const int Inf = 1<<30;int Vis[MAXN],Dist[MAXN],Map[MAXN][MAXN],Ans,MIN;int N,M;int x,y,z;void Initial(){Ans = 0;M = (N * (N – 1) / 2);fill(Vis,Vis + MAXN,0);memset(Map,0,sizeof(Map));//fill(Dist,Dist + MAXN,Inf);}void Deal(){Vis[1] = 1; for(int i = 1;i <= N;i++)//假定从编号1开始找 Dist[i] = Map[i][1];}void Prim(){Deal();int i,j,k;for(i = 2;i <= N;i++){k = i;MIN = Inf;for(j = 2;j <= N;j++)//找出到A集合的最短距离MIN和编号kif(!Vis[j] && Dist[j] < MIN)MIN = Dist[j],k = j;Ans += MIN;Vis[k] = 1;//标记 for(j = 2;j <= N;j++)//更新其他点j到A集合的最短距离Dist[j]if(Map[j][k] < Dist[j])Dist[j] = Map[j][k];}printf("%d\n",Ans);}int main(){while(scanf("%d",&N),N){Initial();for(int i = 1;i <= M;i++){scanf("%d%d%d",&x,&y,&z);Map[x][y] = Map[y][x] = z;//无向图 }Prim(); }return 0;}
方法 3 :
#include <iostream>#include <cstdio>#include <queue>#include <algorithm>#include <cstring>using namespace std;const int MAXN = 105;const int Inf = 1<<30;int Vis[MAXN],Dist[MAXN],Map[MAXN][MAXN],Ans,MIN;int N,M;int x,y,z;struct Node{int v,len;bool friend operator <(Node x,Node y){return x.len > y.len;}};void Initial(){Ans = 0;M = (N * (N – 1) / 2);fill(Vis,Vis + MAXN,0);fill(Dist,Dist + MAXN,Inf);memset(Map,0,sizeof(Map));}void Prim(){priority_queue<Node>P;//用优先队列,可以减少一定的运行时间Node t;t.v = 1,t.len = 0;P.push(t);while(!P.empty()){t = P.top();P.pop();if(Vis[t.v])continue;Vis[t.v] = 1;Ans += t.len;for(int i = 1;i <= N;i++)if(!Vis[i] && Map[i][t.v] < Dist[i]){Node p;Dist[i] = Map[i][t.v];p.v = i,p.len = Map[i][t.v];P.push(p);}}printf("%d\n",Ans);}int main(){while(scanf("%d",&N),N){Initial();for(int i = 1;i <= M;i++){scanf("%d%d%d",&x,&y,&z);Map[x][y] = Map[y][x] = z;//无向图 }Prim(); }return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
蝙蝠黑暗中闯荡，树木默默的成长，蝴蝶破蛹后飞翔，
