首页 > 代码库 > 最小生成树——最短网络Agri-Net

最小生成树——最短网络Agri-Net

最短网络Agri-Net
 
【问题描述】
  农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了用最小的消费,他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000。
【输入格式】
 
第一行:
农场的个数,N3<=N<=100)。
第二行..结尾
 

 

 

后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上,他们是N行,每行N个用空格分隔的数组成,实际上,他们限制在80个字符,因此,某些行会紧接着另一些行。当然,对角线将会是0,因为不会有线路从第i个农场到它本身。

 

 

 

【输出格式】
    只有一个输出,其中包含连接到每个农场的光纤的最小长度。
【输入样例】agrinet.in
    4
    0  4  9  21
    4  0  8  17
    9  8  0  16
    21 17 16  0
【输出样例】agrinet.out
  28
 
 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5  6 struct point{ 7     int x; 8     int y; 9     int w;10 }a[10000];11 int dad[101];12 int n,m,x,k,tot;13 14 int find(int x)15 {16     if(dad[x]!=x) dad[x]=find(dad[x]);17     return dad[x];18 }19 20 void unionn(int a,int b)21 {22     int r1=find(a);23     int r2=find(b);24     if(r1!=r2)25     dad[r1]=r2;26 }27 28 int cmp(const point &a,const point &b)29 {30     if(a.w<b.w) return 1;31     else return 0;32 }33 34 int main()35 {36     cin>>n;37     for(int i=1;i<=n;i++)38       for(int j=1;j<=n;j++){39           cin>>x;40           if(x!=0){41               m++;42               a[m].x=i,a[m].y=j,a[m].w=x;43           }44       }45     for(int i=1;i<=n;i++)46      dad[i]=i;47     sort(a+1,a+m+1,cmp);48     for(int i=1;i<=m;i++){49         if(find(a[i].x)!=find(a[i].y)){50             unionn(a[i].x,a[i].y);51             tot+=a[i].w;52             k++;53         }54         if(k==n-1) break;55     }56     cout<<tot;57     return 0;58 }

 

最小生成树——最短网络Agri-Net