学步园

很神奇的kruakal用法，枚举最小的边，然后kruakal找到一条可行路径，记录差值比较

看了解题报告都有点晕，自己绝对想不到这种用法。。。。。

code：

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 0x3fffffff;

int n,m,fa[201],rank[201];

struct node
{
    int from,to,w;
}p[1001];
bool cmp(const node x,const node y)
{
    return x.w<y.w;
}

int find(int k)
{
    if(k!=fa[k])
    {
        fa[k]=find(fa[k]);
    }
    return fa[k];
}
void merge(int x,int y)
{
    if(x==y)
    {
        return ;
    }
    if(rank[x]<rank[y])
    {
        fa[x]=y;
    }else{
        fa[y]=x;
        if(rank[x]==rank[y])
        {
            rank[x]++;
        }
    }
}

int main()
{
    int i,j,a,b,x,y,ans,cas;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&p[i].from,&p[i].to,&p[i].w);
        }
        sort(p+1,p+m+1,cmp);
        scanf("%d",&cas);
        while(cas--)
        {
            scanf("%d%d",&a,&b);
            ans=INF;
            for(i=1;i<=m;i++)
            {
                for(j=1;j<=n;j++)
                {
                    fa[j]=j;
                    rank[j]=0;
                }
                for(j=i;j<=m;j++)
                {
                    x=find(p[j].from);
                    y=find(p[j].to);
                    merge(x,y);
                    if(find(a)==find(b))
                    {
                        x=p[j].w-p[i].w;
                        if(x<ans)
                        {
                            ans=x;
                        }
                        break;
                    }
                }
                if(j==m+1)
                {
                    break;
                }
            }
            if(ans==INF)
            {
                puts("-1");
            }else{
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}