POJ 2485

 1 #include<iostream>
 2 #define MAXN 505
 3 #define inf 1000000000
 4 using namespace std;
 5 typedef int elem_t;
 6 int _m[MAXN][MAXN];
 7 int pre[MAXN];
 8 elem_t prim(int n,elem_t mat[][MAXN],int* pre);
 9 int main()
10 {
11     //freopen("acm.acm","r",stdin);
12     int num;
13     int i;
14     int j;
15     int min = inf; 
16     int time;
17     scanf("%d",&time);
18     while(time --)
19     {
20         scanf("%d",&num);
21         min = 0; 
22         for(i = 0; i < num; ++ i)
23         {
24             for(j = 0; j < num; ++ j)
25                 _m[i][j] = inf;
26         }
27         for(i = 0; i < num; ++ i)
28         {
29             for(j = 0; j < num; ++ j)
30             {
31                 scanf("%d",&_m[i][j]);
32             }
33         }
34         prim(num,_m,pre);
35         for(i  = num-1; i >= 0; -- i)
36         {
37             j = i;
38             while(pre[j] != -1)
39             {
40                 if(_m[pre[j]][j] > min)
41                     min = _m[pre[j]][j];
42                 j = pre[j];
43             }
44         }
45         cout<<min<<endl;
46     }
47 }
48 
49 
50 
51 ////////////////////////////////////////////////
52 
53 elem_t prim(int n,elem_t mat[][MAXN],int* pre){
54     elem_t min[MAXN],ret=0;
55     int v[MAXN],i,j,k;
56     for (i=0;i<n;i++)
57         min[i]=inf,v[i]=0,pre[i]=-1;
58     for (min[j=0]=0;j<n;j++){
59         for (k=-1,i=0;i<n;i++)
60             if (!v[i]&&(k==-1||min[i]<min[k]))
61                 k=i;
62         for (v[k]=1,ret+=min[k],i=0;i<n;i++)
63             if (!v[i]&&mat[k][i]<min[i])
64                 min[i]=mat[pre[i]=k][i];
65     }
66     return ret;
67 }