usaco_agrinet.cpp

来自「usaco自己做的1到5章的代码」· C++ 代码 · 共 60 行

/*
ID: wangyuc2
PROG: agrinet
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <cmath>
#include <memory>
#include <iomanip>
#define cin fin

using namespace std;
ifstream fin("agrinet.in");
ofstream fout("agrinet.out");

int main()
{  
    int a[100][100]; 
    int closet[100];
    int lowcost[100];
    int i,j,n,k,min;
    long int sum=0;
    memset(closet,0,sizeof(closet));
    cin>>n;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        cin>>a[i][j];
    lowcost[0]=0;
    for(i=1;i<n;i++)
      {lowcost[i]=a[0][i];
       closet[i]=1;
      }
    for(i=1;i<n;i++)
    {min=0x7fffffff;
    // j=-1;
     for(k=1;k<n;k++)
     {
         if(closet[k] && lowcost[k]<min && lowcost[k]!=0)
         {
             min=lowcost[k];
             j=k;
         }
	 }
         lowcost[j]=0;
         sum+=a[closet[j]-1][j];
         for(k=1;k<n;k++)
         {
             if(closet[k] && a[k][j]<lowcost[k] && a[k][j]>0)
             {
                 lowcost[k]=a[k][j];
                 closet[k]=j+1;
             }
         }
    }
    fout<<sum<<endl;
//    system("PAUSE");
    return 0;
}