poj 3522 Slim Span(Kruskal+매 거 진)

제목 링크: http://poj.org/problem?id=3522
제목 의 대의: 무방 향 연결 도 에서
                    최대 변 과 최소 변 차 의 생 성 트 리 를 구하 십시오.
문제 풀이 방향: 최대 변 과 최소 변 차 생 성 트 리
                    최소 변 과 최대 변 의 길이 가 가장 가깝다 는 얘 기다.
                    한 변 을 생 성 트 리 의 가장 작은 변 으로 만 들 고 가장 큰 변 이 가장 작은 변 에 가 까 운 유일한 변 이 존재 합 니 다.
                    모든 변 을 작은 것 부터 큰 것 까지 정렬 합 니 다.
                    차이 가 가장 작은 최대 변 은 반드시 최소 변 뒤에 있다.
                    그리고 이 생 성 트 리 를 구성 하 는 마지막 변!
                    최소 변 에서 m-n+2 작은 변 으로 구 성 된 생 성 트 리 를 매 거 하여 차이 가 가장 작은 것 을 찾 습 니 다.
오류 점:      최소 변 과 최대 변 은 같은 변 일 수 있 습 니 다.
코드:

#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;    //       
                    }
                    break;
                }
            }
        }
        if(min!=INF)  printf("%d
",min);
        else   printf("-1
");
    }
    return 0;
}

비고:오리지널 글,전재 출처 를 밝 혀 주 십시오.