整理板子的时候翻出来的题，Kruskal板子题。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<string> 7 #include<stack> 8 #include<queue> 9 #include<vector> 10 #include<cstdlib> 11 //#include<windows.h> 12 #define first fi 13 #define second se 14 using namespace std; 15 typedef long long ll; 16 const int N = 1e6+10; 17 const int INF = 0x3f3f3f3f; 18 const int inf = - INF; 19 const int mod = 1e9+7; 20 const double pi = acos(-1.0); 21 int n,m; 22 int father[505]; 23 void init(){ 24 m=0; 25 memset(father,-1,sizeof(father)); 26 } 27 struct node { 28 int u,v,w; 29 node(){} 30 node(int u,int v, int w):u(u),v(v),w(w){} 31 bool operator < (const node &rhs)const{ 32 return w < rhs.w; 33 } 34 }edge[N]; 35 int Find(int x){ 36 return father[x]==-1?x:father[x]=Find(father[x]); 37 } 38 int Kruskal(){ 39 int maxn=-1; 40 int cnt=0; 41 for(int i=0;i<m;i++){ 42 int u=edge[i].u; 43 int v=edge[i].v; 44 if(Find(u)!=Find(v)){ 45 father[Find(u)]=Find(v); 46 maxn=max(maxn,edge[i].w); 47 if(++cnt>=n-1) return maxn; 48 } 49 } 50 return -1; 51 } 52 int main(){ 53 int T; 54 scanf("%d",&T); 55 while(T--){ 56 scanf("%d",&n); 57 init(); 58 int t; 59 for(int i=1;i<=n;i++){ 60 for(int j=1;j<=n;j++){ 61 scanf("%d",&t); 62 edge[m++]=node(i,j,t); 63 } 64 } 65 sort(edge,edge+m); 66 printf("%d\n",Kruskal()); 67 } 68 //system("pause"); 69 return 0; 70 }