poj 2485 Highways

 1 /*求最小生成树的最大权边*/
 2 
 3 #include <iostream>
 4 #include <cstdio>
 5 #include <cstring>
 6 using namespace std;
 7 const int MAX=550;
 8 const int INF=0xfffffff;
 9 int g[MAX][MAX];
10 int vis[MAX]; //标记数组，没有加入时为0，加入后为1
11 int dis[MAX]; //记录树到每个顶点的最小距离，会不断更新
12 int t,n;
13 int prim(int start)
14 {
15     int i,j,k,Min,Max=0;
16     memset(vis,0,sizeof(vis));
17     vis[start]=1;//将第一个顶点加入树
18     for(i=0;i<n;i++)
19     {
20         dis[i]=g[start][i]; //计算其他顶点距离第一个顶点的最小距离
21     }
22     for(i=1;i<n;i++)  // 注意循环次数
23     {
24         Min=INF,k=-1;
25         for(j=0;j<n;j++) //找最小边
26         {
27             if(!vis[j]&&dis[j]<Min)
28             {
29                 Min=dis[j];
30                 k=j;
31             }
32         }
33         vis[k]=1;
34         Max=max(Min,Max);  // 更新树的最大权值
35         for(j=0;j<n;j++)  //更新权值
36         {
37             if(!vis[j]&&dis[j]>g[k][j])
38                 dis[j]=g[k][j];
39         }
40     }
41     return Max;
42 }
43 int main()
44 {
45     scanf("%d",&t);
46     while(t--)
47     {
48         scanf("%d",&n);
49         memset(dis,INF,sizeof(dis));
50         for(int i=0;i<n;i++)
51         {
52             for(int j=0;j<n;j++)
53                 scanf("%d",&g[i][j]);
54         }
55         printf("%d\n",prim(0));
56     }
57     return 0;
58 }