最小生成树之Prim的应用

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MAX 100000000
 4 int map[505][505];//邻接矩阵
 5 int dis[505];//距离 并且指这条边是以dis[i]的i为结尾的
 6 int visited[505];
 7 int n,m;
 8 
 9 int prim()
10 {
11     int i,j,k,ans=0,min,t;
12     memset(visited,0,sizeof(visited));//起初标记所有点都未被访问
13     for(i=1;i<=n;i++)
14         dis[i]=map[1][i];//所有最小权值边起初都是以相同的起始点1开始
15     visited[1]=1;//从1开始访问
16     for(i=1;i<n;i++)//因为是最小生成树 所以当有n个顶点的时候 只有n-1条边
17     {
18         min=MAX;//将Min设置的 无穷大 以便来标记
19         for(j=2;j<=n;j++)
20         {
21             if( !visited[j] && dis[j]<min )//j的要求未被访问 并且可以得到相对最小距离
22             {
23                 min=dis[j];
24                 t=j;
25             }
26         }
27         if(min==Max)//如果这个if成立相当于 上面没有一个j进入MST中 所有可以直接break
28               break;
29         ans+=min;
30         visited[t]=1;
31 
32         for(k=2;k<=n;k++)
33         {
34             if( !visited[k] && dis[k]> map[t][k] )//这边 我用大于号 才能刷新最下值
35                 dis[k]=map[t][k];
36         }
37 
38     }
39     return ans;
40 }
41 
42 int main()
43 {
44     int t,a,b,c,i,j,min;
45     scanf("%d",&t);
46     while (t--)
47     {
48         scanf("%d %d",&n,&m);
49         for(i=1;i<=n;i++)
50         {
51             for(j=1;j<=n;j++)
52                 map[i][j]=MAX;
53         }
54         for(i=1;i<=m;i++)
55         {
56             scanf("%d%d%d",&a,&b,&c);
57             map[a][b]=map[b][a]=c;
58         }
59         min=MAX;
60         for(i=1;i<=n;i++)
61         {
62             scanf("%d",&a);
63             if(a<min)
64                 min=a;
65         }
66         printf("%d\n",min+prim());
67     }
68 }