POJ 1258 Agri-Net(Prim)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int inf=11111111;
 6 int n,res;
 7 int dist[105],f[105][105];
 8 int vis[105];
 9 void prim(){
10     int v=0;
11     memset(vis, 0, sizeof(vis));
12     for (int i=1; i<=n; i++)    dist[i]=inf;
13     dist[1]=0;
14     for (int i=1; i<=n; i++) {
15         int Min=inf;
16         for (int j=1; j<=n; j++) {
17             if(dist[j]<Min && !vis[j]){
18                 Min=dist[j];
19                 v=j;
20             }
21         }
22         vis[v]=1;
23         res+=dist[v];
24         for (int j=1; j<=n; j++) {
25             dist[j]=min(dist[j],f[v][j]);//算法核心，是求遍历点到部分最小生成树的最小距离，而不是单个点
26         }
27     }
28 }
29 int main(){
30     while (scanf("%d",&n)!=EOF && n) {
31         res=0;
32         for (int i=1; i<=n; i++) {
33             for (int j=1; j<=n; j++) {
34                 scanf("%d",&f[i][j]);
35             }
36         }
37         prim();
38         printf("%d\n",res);
39     }
40     return 0;
41 }