题目大意：
很多村庄，每两个村庄之间都可以建公路，要求建完之后，必须可以从任意一个村庄通过公路到任意另一个村庄。 现在他想问，怎么建这个公路可以使这些条路中最长的那一条的长度最短。
思路：

类似于Kruskal算法，所有边从小到大排序，枚举每一条边建公路，直到所有的点都能连通为止（用并查集判断）

#include #include #include #include #include #define N 550 using namespace std; struct edge { int s;int e;int v; }a[N*N]={0}; int dis[N][N]={0}; int n; int m; int boss[N]={0};//i的父节点为boss[i] void biuld()//建立并查集 { for(int i=1;i<=n;i++) { boss[i]=i; } } int bossnum()//返回并查集的树的个数 { int s=0; for(int i=1;i<=n;i++) { if(boss[i]==i)s++; } return s; } void input() { scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&dis[i][j]); } } m=1;//及路边的总数 for(int i=1;i<=n;i++)//把所有的无向边存到edge数组里面 { for(int j=i+1;j<=n;j++) { a[m].v=dis[i][j]; a[m].s=i; a[m].e=j; m++; } } } bool cmp(edge c,edge b) { if(c.v>b.v)return 0; return 1; } void connect(int x,int y) { if(boss[x]==x&&boss[y]==y) { boss[x]=y; return; } boss[x]=boss[boss[x]]; boss[y]=boss[boss[y]]; connect(boss[x],boss[y]); } int my_kruskal() { int max=0; biuld(); for(int i=1;i>cs; while(cs--) { input(); sort(a+1,a+m,cmp); /*for(int i=1;i
然后我去网上查了一下别人的代码，我查到的所有人都说是求最小生成树的最长边的权值，但是如果真的是这样，那这一组数据他绝对是过不了的。
1
4
0 2 3 2
1 0 2 3
3 2 0 2
2 3 2 0
但是，我把他们的代码复制下来，然后用这组数据试了一下，发现居然都能得出正确答案，也不知道他们代码都是怎么写的。
现在举例说明：最小生成树的最长边权值并不等价于使图连通的所有边的最长边的可能取到的最小值。

如本图所示，即上组测试数据的图，显然，最小生成树的所有边的和应该是7，此时最长边应该是3，但是，但是，但是，四条权值为2的边就可以使图连通，最长边的可能取到的最小值为2！

备注：代码完全手打，一次ac，并查集魔板（魔法的魔）回来一定要好好整理一个。