题目描述

约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000

输入输出格式

输入格式：

 

第一行： 农场的个数，N（3<=N<=100）。

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

 

输出格式：

 

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

 

输入输出样例

输入样例#1： 

40 4 9 214 0 8 179 8 0 1621 17 16 0

输出样例#1： 

28 模板

#include 
       
        using namespace std;typedef long long ll;#define inf 2147483647const ll INF = 0x3f3f3f3f3f3f3f3fll;#define ri register inttemplate 
        
          inline T min(T a, T b, T c){    return min(min(a, b), c);}template 
         
           inline T max(T a, T b, T c){    return max(max(a, b), c);}template 
          
            inline T min(T a, T b, T c, T d){    return min(min(a, b), min(c, d));}template 
           
             inline T max(T a, T b, T c, T d){    return max(max(a, b), max(c, d));}#define pi acos(-1)#define me(x, y) memset(x, y, sizeof(x));#define For(i, a, b) for (int i = a; i <= b; i++)#define FFor(i, a, b) for (int i = a; i >= b; i--)#define mp make_pair#define pb push_backconst int maxn = 100005;#define mod 100003const int N=10005;// name*******************************struct edge{    int from,to,dis;} e[N];int pre[N];int Rank[N];int tot=0;int ans=0;int n;// function******************************bool cmp(edge x,edge y){    return x.dis
            
             Rank[t2]) pre[t2]=t1; else pre[t1]=t2; if(Rank[t1]==Rank[t2]) Rank[t2]++;}//***************************************int main(){// freopen("test.txt", "r", stdin); cin>>n; For(i,1,n)init(i); For(i,1,n) For(j,1,n) { int x; scanf("%d",&x); if(i!=j) { e[++tot].from=i; e[tot].to=j; e[tot].dis=x; } } sort(e+1,e+1+tot,cmp); int cnt=0; For(i,1,tot) { if(find(e[i].from)!=find(e[i].to)) { unionone(e[i].from,e[i].to); ans+=e[i].dis; cnt++; if(cnt==n-1)break; } } cout<