| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 23343 | Accepted: 10015 |
3 0 990 692 990 0 179 692 179 0 1 1 2
179
题目描述：
有N个村庄,从1到N编号,建立一些道路,这样任意两个村庄能连接到对方。我们说两个村庄A和B是连接,当且仅当有A和B之间的道路,或存在C这样的一个村庄之间有一条路A和C,C和B连接。
我们知道,已经有一些道路之间的一些村庄,你的工作是构建道路,所有的村庄都连接和道路建设是最小的长度。
输入描述：
第一行是一个整数N(3 < = N < = 100),这是村庄的数量。然后N行,其中包含N个整数,第i和j N个整数的距离(距离应该是整数在[1000])j村之间我和村庄。
还有一个整数(0 < = Q < = N *(N + 1)/ 2)。然后再问行,每一行包含两个整数a和b(1 < = < b < = N),这意味着路村和村b之间已经建立了。
输出描述：
你应该输出一行包含一个整数,它是所有道路的长度建立连接,这样所有的村庄,这个值是最低。
1 /* 2 很简单的最小生成树 3 */ 4 #include<cstdio> 5 #include<cstring> 6 #include<iostream> 7 #include<algorithm> 8 using namespace std; 9 struct node{int x,y,t;}e[20010]; 10 inline void read(int &x) 11 { 12 int f=1;x=0;char ch=getchar(); 13 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 14 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15 x=x*f;return ; 16 } 17 bool cmp(const node &a,const node &b){return a.t<b.t;} 18 int n,m,x,y,ans=0,fa[110],sum=0; 19 int find(int x) 20 { 21 if(fa[x]==x)return x; 22 return fa[x]=find(fa[x]); 23 } 24 void add(int x,int y) 25 { 26 int xx=find(x),yy=find(y); 27 fa[xx]=yy; 28 } 29 int main() 30 { 31 read(n); 32 for(int i=1;i<=n;i++)fa[i]=i; 33 for(int i=1;i<=n;i++) 34 for(int j=1;j<=n;j++) 35 { 36 sum++; 37 read(e[sum].t); 38 e[sum].x=i;e[sum].y=j; 39 } 40 read(m); 41 for(int i=1;i<=m;i++) 42 { 43 read(x),read(y); 44 e[++sum].x=x; 45 e[sum].y=y; 46 e[sum].t=0; 47 } 48 sort(e+1,e+sum+1,cmp); 49 m=0; 50 for(int i=1;i<=sum;i++) 51 { 52 int xx=find(e[i].x),yy=find(e[i].y); 53 if(xx!=yy) 54 { 55 ans+=e[i].t; 56 add(xx,yy); 57 m++; 58 } 59 if(m==n-1)break; 60 } 61 printf("%d\n",ans); 62 return 0; 63 }
原文：http://www.cnblogs.com/EvilEC/p/6364355.html