并查集 +kruskal
#include"stdio.h"
#include"string.h"
#include"stdlib.h"

int n,m;
struct A
{
int a,b;
int len;
int flag;
}eage[15555];
int set[1011];

struct B
{
int a,b;
}eage2[1111];
int K;

int cmp1(const void *a,const void *b)
{／／排序的目的是因为输出要求
struct A *c,*d;
c=(struct A *)a;
d=(struct A *)b;
return c->len-d->len;//直接相减得到从小到大排序
}
int cmp2(const void *a,const void *b)
{
struct B *c,*d;
c=(struct B *)a;
d=(struct B *)b;
if(c->a!=d->a) return c->a-d->a;
return c->b-d->b;
}
int MIN(int a,int b)
{
return a>b?b:a;
}
int MAX(int a,int b)
{
return a>b?a:b;
}

void build(int num)
{／／建立并查集，ｓｅｔ数组来表示各个元素的集合代表元素
int i;
for(i=1;i<=num;i++) set[i]=i;
}
int find(int k)
{／／确定元素的代表元素
if(set[k]==k) return k;
set[k]=find(set[k]);
return set[k];
}
void Union(int f1,int f2)
{／／使用路径压缩以后，路径长度都会被压缩，因此不需要设置另外的数组／／来表示集合树的高度，进而判断哪个集合接在哪个集合的后面
set[f1]=f2;
}

int M_len,ans;
void Kruskal()
{
int i;
int f1,f2;
int count;

count=1;
for(i=0;i<m;i++)
{
if(count==n) break;

f1=find(eage[i].a);
f2=find(eage[i].b);
if(f1==f2) continue;
count++;
eage[i].flag=1;
Union(f1,f2);
ans+=eage[i].len;

eage2[K].a=eage[i].a;
eage2[K].b=eage[i].b;
K++;
}

for(i=m-1;i>=0;i--) if(eage[i].flag) {M_len=eage[i].len;break;}
}
int main()
{
int i;
int a,b,c;
int min,max;
while(scanf("%d%d",&n,&m)!=-1)
{
build(n);

for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
eage[i].flag=0;
min=MIN(a,b);／／因为输出需要，对边的起点，终点进行比较
max=MAX(a,b);
eage[i].a=min;／／这里存储边的方式类似邻接表，只是没有
eage[i].b=max;／／节点的ＮＥＸＴ信息
eage[i].len=c;
}

ans=0;
M_len=0;
qsort(eage,m,sizeof(eage[0]),cmp1);
K=0;
Kruskal();

printf("%d\n",M_len);
printf("%d\n",n-1);

qsort(eage2,K,sizeof(eage2[0]),cmp2);
for(i=0;i<K;i++) printf("%d %d\n",eage2[i].a,eage2[i].b);
}
return 0;
}

UnionFind2492