poj 2485 Highways 求最小生成树中的最大边

英语一定要好啊，不好就悲剧了。。。我开始都没看懂，后来才懂了。。。一定要仔细啊！！！

注意要求，0的意思是不通。然后我用的kruskal算法写的，用邻接矩阵搞的，然后再从矩阵中读边。

裸地最小生成树。

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <string.h>
  5 #define MAXN 10000
  6 #define MAXM 50000
  7 using namespace std;
  8 int point[500+10][500+10];
  9 struct edge
 10 {
 11    int u,v,w;
 12 }edges[MAXM];
 13 int parent[MAXN];
 14 int n,m;
 15 int i,j;
 16 int maxx;
 17 
 18 //并查集
 19 void UFset()
 20 {
 21 
 22      for(i=1;i<=n;i++)
 23      parent[i]=-1;
 24 }
 25 int Find(int x)
 26 {
 27     int s;
 28     for(s=x;parent[s]>=0;s=parent[s])  ;
 29     while(s!=x)
 30     {
 31        int tmp=parent[x];
 32        parent[x]=s;
 33        x=tmp;
 34     }
 35     return s;
 36 }
 37 void Union(int R1,int R2)
 38 {
 39      int r1=Find(R1),r2=Find(R2);
 40      int tmp=parent[r1]+parent[r2];
 41      if(parent[r1]>parent[r2])
 42      {
 43        parent[r1]=r2;
 44        parent[r2]=tmp;
 45      }
 46      else
 47      {
 48        parent[r2]=r1;
 49        parent[r1]=tmp;
 50      }
 51      return;
 52 }
 53 //并查集
 54 bool cmp(edge a,edge b)
 55 {
 56     return a.w<b.w;
 57 }
 58 void Kruskal()
 59 {
 60     maxx=0;
 61     int sumweight=0;
 62     int num=0;
 63     int u,v;
 64     UFset();
 65     for(i=0;i<m;++i)
 66     {
 67       u=edges[i].u;v=edges[i].v;
 68       if(Find(u)!=Find(v))
 69       {
 70         if(edges[i].w>maxx) maxx=edges[i].w;
 71         sumweight+=edges[i].w; ++num;
 72         Union(u,v);
 73       }
 74     }
 75     printf("%d\n",maxx);
 76 }
 77 
 78 int main()
 79 {
 80    int t,count;
 81    while(scanf("%d",&t)!=EOF)
 82    {
 83       memset(point,0,sizeof(point));
 84       while(t--)
 85       {
 86          scanf("%d",&n);
 87          for(i=0;i<n;++i)
 88           for(j=0;j<n;++j)
 89           {
 90              scanf("%d",&point[i][j]);
 91              if(point[i][j]==0) point[i][j]=1000000000;
 92           }
 93          m=0;
 94          for(i=0;i<n;++i)
 95           for(j=0;j<=i;++j)
 96           {
 97              if(i==j) continue;
 98              edges[m].u=i+1;
 99              edges[m].v=j+1;
100              edges[m].w=point[i][j];
101              m++;
102           }
103          sort(edges,edges+m,cmp);
104       Kruskal();
105     }
106    }
107    return 0;
108 }