Agri-Net(prim)

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int maxn=110;
 4 const int INF = 1<<28;
 5 int map[maxn][maxn];
 6 int dis[maxn],vis[maxn];
 7 int n,sum;
 8 void prim()
 9 {
10     int pos;
11     for (int i = 1; i <= n; i ++)
12     {
13         dis[i] = map[1][i];
14     }
15     vis[1] = 1;
16     for (int i = 1; i <= n-1; i ++)
17     {
18         int min = INF;
19         for (int j = 1; j <= n; j ++)
20         {
21             if (!vis[j] && dis[j] < min)
22             {
23                 min = dis[j];
24                 pos = j;
25             }
26         }
27         sum += min;
28         vis[pos] = 1;
29         for (int j = 1; j <= n; j ++)
30         {
31             if (!vis[j] && dis[j] > map[pos][j])
32                 dis[j] = map[pos][j];
33         }
34     }
35 }
36 void init()
37 {
38     sum = 0;
39     for (int i = 0; i <= n; i ++)
40     {
41         for (int j = 0; j <= n; j ++)
42         {
43             map[i][j] = INF;
44         }
45         map[i][i] = 0;
46         vis[i] = 0;
47     }
48 }
49 int main()
50 {
51 
52     while(~scanf("%d",&n))
53     {
54         init();
55         for (int i = 1; i <= n; i ++)
56         {
57             for (int j = 1; j <= n; j ++)
58             {
59                 scanf("%d",&map[i][j]);
60             }
61         }
62         prim();
63         printf("%d
",sum);
64     }
65     return 0;
66 }
View Code