最短網絡Agri-Net

【例4-11】、最短網絡Agri-Net

【問題描述】

農民約翰被選為他們鎮的鎮長！他其中一個競選承諾就是在鎮上建立起互聯網，并連接到所有的農場。當然，他需要你的幫助。約翰已經給他的農場安排了一條高速的網絡線路，他想把這條線路共享給其他農場。為了用最小的消費，他想鋪設最短的光纖去連接所有的農場。你將得到一份各農場之間連接費用的列表，你必須找出能連接所有農場并所用光纖最短的方案。每兩個農場間的距離不會超過100000。

【輸出格式】

只有一個輸出，其中包含連接到每個農場的光纖的最小長度。

【輸入樣例】agrinet.in

4

0? 4? 9? 21

4? 0? 8? 17

9? 8? 0? 16

21 17 16? 0

【輸出樣例】agrinet.out

28

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct k{
    int x,y,v;
    
}a[10000];
int fa[1000];
int find(int x)
{
    if(fa[x]!=x)
    {fa[x]=find(fa[x]);
    return fa[x];
    }
    else
    return x;
}
void un(int x,int y)
{
    fa[x]=y;
}
int cmp( k a, k b)      
{
     if (a.v < b.v) return 1;
        else return 0; 
}
int main()
{
    int s,m=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=n;j++)
          {
              cin>>s;
              if(s!=0)
               {
                   m++;
                   a[m].x=i;
                   a[m].y=j;
                   a[m].v=s;
               }
          }
     }
     for(int i=1;i<=n;i++)
      {
          fa[i]=i;
      }
      sort(a+1,a+m+1,cmp);
      int k=0,tot=0;
     for(int i=1;i<=m;i++)
      {
          int r=find(a[i].x);
          int rr=find(a[i].y);
          if(r!=rr)
           {
               un(r,rr);
               tot+=a[i].v;
               k++;
           }
        if(k==n-1)
         {
             break;
         }
      }
      cout<<tot;
    return 0;
}

?

【輸入格式】

第一行：	農場的個數，N（3<=N<=100）。
第二行..結尾	后來的行包含了一個N*N的矩陣,表示每個農場之間的距離。理論上，他們是N行，每行由N個用空格分隔的數組成，實際上，他們限制在80個字符，因此，某些行會緊接著另一些行。當然，對角線將會是0，因為不會有線路從第i個農場到它本身。