poj 2485 Highways 最小生成树

题意比较明显。。。就是求最小生成树里的最长路，其实用dijks也可以。。。
View Code
 1 #include <iostream>
 2 #include <stdio.h>
 3 #define max 65536;
 4 using namespace std;
 5 
 6 int map[505][505];
 7 int ans;
 8 void init(int n)
 9 {
10     int i,j;
11     for(i = 1;i <= n;i++)
12     {
13         for(j = 1;j <= n;j++)
14         {
15             map[i][j] = max;
16         }
17     }
18 }
19 int prim(int n)
20 {
21     int vis[505] = {0},i,j,k,pre,min;
22     int d[505];
23     ans = -1;
24     for(i = 2;i <= n;i++)
25     {
26         d[i] = map[1][i];
27     }
28 
29     pre = 1;
30     vis[pre] = 1;
31 
32     for(i = 1;i < n;i++)
33     {
34         min = max;
35         for(j = 2;j <= n;j++)
36         {
37             if(min > d[j] && !vis[j])
38             min = d[j],pre = j;
39         }
40 
41         if(ans < min)ans = min;
42         vis[pre] = 1;
43         for(j = 2;j <= n;j++)
44         if(d[j] > map[pre][j] && !vis[j])
45         d[j] = map[pre][j];
46     }
47     return ans;
48 }
49 int main()
50 {
51     int t,n,i,j,w;
52     cin>>t;
53     while(t--)
54     {
55         cin>>n;
56         init(n);
57         for(i = 1;i <= n;i++)
58         {
59             for(j = 1;j <= n;j ++)
60             {
61                 cin>>map[i][j];
62             }
63         }
64 
65         cout<<prim(n)<<endl;
66     }
67     return 0;
68 }