poj 3522 Slim Span (Kruskal+枚举)

题目大意：在一个无向联通图中

求一棵最大边与最小边差值最小的生成树

解题思路：最大边与最小边差值最小的生成树

换言之使得最小边与最大边的长度最接近

任取一条边为生成树最小的边，唯一存在一条最大边最接近最小的边

对所有的边从小到大排序

差值最小的最大边一定在最小边后面

并且是构成这个生成树的最后一条边！

枚举最小边到第m－n＋2小边组成的生成树，找出差值最小的

易错点：最小边和最大边可能是同一条边

代码：

[cpp]

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define MAX 101

#define MAX_2 9000

#define INF 0x3f3f3f3f

typedef struct snode{

int x;

int y;

int s;

}span;

int father[MAX];

int comp(const void *a,const void *b)

{

span *pa=(span *)a;

span *pb=(span *)b;

return pa->s-pb->s;

}

void Empty(int n)

{

int i;

for(i=1;i<=n;i++)

father[i]=i;

}

int Find(int x)

{

int s,j;

s=x;

while(x!=father[x]) x=father[x];

while(s!=x)

{

j=father[s];

father[s]=x;

s=j;

}

return x;

}

void Union(int R1,int R2)

{

int r1,r2;

r1=Find(R1);

r2=Find(R2);

if(r1!=r2) father[r1]=r2;

}

int main ()

{

int n,m,i,j,min,start,end,num,a;

while(scanf("%d%d",&n,&m)!=EOF)

{

span spantree[MAX_2];

if(m==0&&n==0)

break;

for(i=0;i<m;i++)

{

scanf("%d%d%d",&spantree[i].x,&spantree[i].y,&spantree[i].s);

}

qsort(spantree,m,sizeof(spantree[0]),comp); //把边从小到大排序

for(i=0,end=0,start=0,min=INF;i<m-n+2;i++) //最多m-n+2个生成树

{

Empty(n);

for(j=i,num=0;j<m;j++)

{

if(Find(spantree[j].x)!=Find(spantree[j].y))

{

Union(spantree[j].x,spantree[j].y);

num++; //某个生成树的第num条边

if(num==1) //第一条最小，num-1条最大

start=spantree[j].s;

if(num==n-1) //易错点**：是if不是else if,因为可能只有一条边

end=spantree[j].s;

}

if(num==n-1)

{

a=end-start;

if(a<min)

{

min=a; //找到最小的差值

}