http://poj.org/problem?id=1861
#include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; #define maxn 1001 #define maxm 15001 struct edge { int u,v,w; } edges[maxm]; int parent[maxn],ans[maxn]; int i,j,N,M; int maxedge,num,ai; void ufset() { for(i=0; i<N; i++) parent[i]=-1; } int find(int x) { int s; for(s=x; parent[s]>=0; s=parent[s]); while(s!=x) { int tmp=parent[x]; parent[x]=s; x=tmp; } return s; } void Union(int R1,int R2) { int r1=find(R1),r2=find(R2); int tmp=parent[r1]+parent[r2]; if(parent[r1]>parent[r2]) { parent[r1]=r2; parent[r2]=tmp; } else { parent[r2]=r1; parent[r1]=tmp; } } int cmp(const void* a,const void* b) { edge aa=*(const edge*)a; edge bb=*(const edge*)b; return aa.w-bb.w; } void kruskal() { int u,v; ufset(); for(i=0; i<M; i++) { u=edges[i].u; v=edges[i].v; if(find(u)!=find(v)) { ans[ai++]=i; if(edges[i].w>maxedge) maxedge=edges[i].w; num++; Union(u,v); } if(num>N-1) break; } } int main() { //freopen("1.txt","r",stdin); while(scanf("%d%d",&N,&M)!=EOF) { for(i=0; i<M; i++) scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w); qsort(edges,M,sizeof(edges[0]),cmp); maxedge=0; num=0; kruskal(); printf("%d\n%d\n",maxedge,num); for(i=0; i<num; i++) printf("%d %d\n",edges[ans[i]].u,edges[ans[i]].v); } return 0; }