Prim基础最小生成树

 1 <span style="font-size:18px;">#include<stdio.h>
 2 #include<string.h>
 3 #define INF 1001
 4 int map[101][101],vis[101],dist[101];
 5 int n;
 6 int prim()
 7 {
 8     int i,j,mincost=0;
 9     for(i=1;i<=n;i++)       //初始化
10         dist[i]=map[1][i];
11     vis[1]=1;
12     for(i=2;i<=n;i++)   //循环n-1次，每次加入一个点
13     {
14         int min=INF,p=1;
15         for(j=1;j<=n;j++)
16         {
17             if(!vis[j]&&dist[j]<min)  
18             {
19                 min=dist[j];
20                 p=j;
21             }
22         }
23         vis[p]=1;                //将p点加入Va中
24         mincost+=min;
25         for(j=1;j<=n;j++)       //对于与p相邻的在Vb集合中的j，更新到j的距离最近的点和距离
26         {
27             if(!vis[j]&&dist[j]>map[p][j])
28                 dist[j]=map[p][j];
29         }
30     }
31     return mincost;
32 }
33 int main()
34 {
35     while(scanf("%d",&n)!=EOF)
36     {
37         memset(map,0,sizeof(map));
38         memset(vis,0,sizeof(vis));
39         int i,j;
40         for(i=1;i<=n;i++)
41             for(j=1;j<=n;j++)
42             scanf("%d",&map[i][j]);
43         int q,a,b;
44         scanf("%d",&q);
45         while(q--)
46         {
47             scanf("%d%d",&a,&b);
48             map[a][b]=0;
49             map[b][a]=0;
50         }
51         int ans=prim();
52         printf("%d\n",ans);
53     }
54     return 0;
55 }
56 </span>