USACO Section 3.1 Agri-Net - [水]最小生成数模板题

赤果果的最小生成树...于是就用Prim水了...

Program:

/*  
ID: zzyzzy12  
LANG: C++  
TASK: agrinet
*/    
#include<iostream>    
#include<istream>
#include<stdio.h>    
#include<string.h>    
#include<math.h>    
#include<stack>
#include<algorithm>    
#include<queue> 
#define oo 2000000000
#define ll long long
using namespace std;   
int n,arc[105][105];
int Prim()
{
     bool used[105];
     int i,k,j,m,p,ans=0;
     memset(used,false,sizeof(used)); 
     used[1]=1;
     for (k=1;k<n;k++)
     {
           m=100000;
           for (i=1;i<=n;i++)
             for (j=1;j<=n;j++)
               if (used[i] && !used[j] && m>arc[i][j])
               {
                      m=arc[i][j];    
                      p=j;        
               }
           used[p]=true;
           ans+=m;                 
     }
     return ans;
}
int main()
{
     freopen("agrinet.in","r",stdin);  
     freopen("agrinet.out","w",stdout);  
     scanf("%d",&n);
     for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) 
           scanf("%d",&arc[i][j]);
     printf("%d\n",Prim()); 
     return 0;   
}