poj 1258 Agri-Net
#include <iostream> using namespace std; int n; int w[101][101]; int lowcost[101]; bool f[101]; int prim(){ memset(f,0,sizeof(f)); memset(lowcost,0,sizeof(lowcost)); f[1]=1; int i,j; for(i=1;i<=n;i++){ lowcost[i]=w[1][i]; } int ans=0; for(i=1;i<n;i++){ int min=100*100*127; int v; for(j=1;j<=n;j++){ if(f[j]==0&&lowcost[j]<min){ min=lowcost[j]; v=j; } } ans+=min; f[v]=1; for(j=1;j<=n;j++){ if(f[j]==0&&w[v][j]<lowcost[j]) lowcost[j]=w[v][j]; } } return ans; } int main(){ while(cin>>n){ int i,j; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ cin>>w[i][j]; } } cout<<prim()<<endl; } return 0; }