整理板子的时候翻出来的题，放在一起写是因为都是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 fi13 #define second se14 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 }

 1258可以直接用2485改改就交，注意要多组输入。

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<string>#include<stack>#include<queue>#include<vector>#include<cstdlib>#include<windows.h>#define first fi#define second seusing namespace std;typedef long long ll;const int N = 1e6+10;const int INF = 0x3f3f3f3f;const int inf = - INF;const int mod = 1e9+7;const double pi = acos(-1.0);ll n,m;ll father[505];void init(){ m=0; memset(father,-1,sizeof(father));}struct node { ll u,v,w; node(){} node(ll u,ll v, ll w):u(u),v(v),w(w){} bool operator < (const node &rhs)const{ return w < rhs.w; }}edge[N]; ll Find(int x){ return father[x]==-1?x:father[x]=Find(father[x]);}ll Kruskal(){ ll sum=0; ll cnt=0; for(ll i=0;i<m;i++){ ll u=edge[i].u; ll v=edge[i].v; if(Find(u)!=Find(v)){ father[Find(u)]=Find(v); sum+=edge[i].w; if(++cnt>=n-1) return sum; } } return -1;}int main(){ //int T; //scanf("%d",&T); while(~scanf("%lld",&n)){//注意多组输入 init(); ll t; for(ll i=1;i<=n;i++){ for(ll j=1;j<=n;j++){ scanf("%lld",&t); edge[m++]=node(i,j,t); } } sort(edge,edge+m); printf("%d\n",Kruskal()); } system("pause"); return 0;}