一道最小生成樹的問題。

　　題目所給的輸入是按矩陣的方式輸入的，顯然這個矩陣關于主對角元對稱，所以只需要存儲一半的數據即可（其實少于一半，主對角元也不用存儲）。對于輸入所給的已修好路的兩個村子，合并它們分別所在的集合（開始的時候思維有漏洞，直接parnt[h]=l,這樣是不對的，應該先找到它們的根進行合并，看來自己思維的嚴密性還是很欠缺）。剩下的直接按照Kruskal算法的思路進行即可，遇到不在同一連通集合的村子，說明兩個村子之間需要修路。

#include<stdio.h> #include<stdlib.h> #define max_town 110 #define max_road 10200 struct edge {int a;int b;int v; }edge[max_road]; int get_root(int),cmp(const void *,const void *),parnt[max_road],sum=0; void unon(int,int); int main() {int n;while(scanf("%d",&n)!=EOF){int i,p=0,q,trash,k;for(i=0,k=0;i<n-1;i++,k++)//輸入部分{int j;for(j=0;j<n;j++){if(j>=k&&i!=j)//存儲主對角元右上方的元素{edge[p].a=i;edge[p].b=j;scanf("%d",&edge[p].v);p++;//已存個數，方便排序}else{scanf("%d",&trash);}}}for(i=0;i<n;i++){scanf("%d",&trash);}//********************************輸入結束for(i=0;i<p;i++)//初始化并查集parnt[i]=i;qsort(edge,p,sizeof(edge[0]),cmp);scanf("%d",&q);for(i=0;i<q;i++){int h,l;scanf("%d%d",&h,&l);h--;l--;
　　　　　　　　/*將已經修通路的村子放入一個連通集合中*/h=get_root(h);l=get_root(l);parnt[h]=l;}for(i=0;i<p;i++){if(get_root(parnt[(edge[i].a)])!=get_root(parnt[(edge[i].b)])){sum+=edge[i].v;unon(edge[i].a,edge[i].b);//修了路之后，將兩個村子放入一個連通集合}}printf("%d\n",sum);sum=0;}return 0; } int get_root(int x) {if(parnt[x]!=x){parnt[x]=get_root(parnt[x]);}return parnt[x]; } void unon(int x,int y) {x=get_root(x);y=get_root(y);if(x!=y){parnt[x]=y;} } int cmp(const void *x,const void *y) {return (*(struct edge *)x).v-(*(struct edge *)y).v; }

轉載于:https://www.cnblogs.com/coredux/archive/2012/04/19/2456235.html

總結

以上是生活随笔為你收集整理的HDU 1102的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。