【HDU - 1598】 find the most comfortable road

题目链接：传送门

题目是一道中文题目，大概题意：给一些双向边，多次询问从起点s，到终点e，（权值max-权值min）的最小值。

本题的正确做法：并查集+思维 （暴力求解，不会超时）      ///并不是最小生成树

做法：题目求最小值与最大值的差值最小，我们可以将权值从小到大排序，然后枚举最小值，

然后往下开始用并查集，如果起点s和终点e在同一棵树上了，那么当前的权值和最小值来更新答案，如果不能构成一棵树，输出-1。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int p[205];

struct node
{
    int s;
    int e;
    int c;

} load[1005];

bool cmp(node a,node b)
{
    return a.c<b.c;
}

int f(int x)
{
    return p[x]==x?x:p[x]=f(p[x]);
}

int main()
{
    int n,m,x,s,e,c;
    while(~scanf("%d %d",&n,&m))
    {
        for(int i=1; i<=m; i++)
        {
            scanf("%d %d %d",&s,&e,&c);
            load[i]=node{s,e,c};
        }
        sort(load+1,load+1+m,cmp);      ///权值排序
        scanf("%d",&x);
        while(x--)
        {
            scanf("%d %d",&s,&e);
            int ans=INT_MAX;
            for(int i=1; i<=m; i++)     ///枚举最小权值
            {
                for(int k=1; k<=n; k++)
                    p[k]=k;
                for(int j=i;j<=m;j++)   ///并查集
                {
                    int q=f(load[j].s),u=f(load[j].e);
                    if(q!=u)
                        p[q]=u;
                    if(f(s)==f(e))  ///如果构成一棵树了，那么当前load[j].c就是权值最大。
                    {
                        ans=min(ans,load[j].c-load[i].c);   ///更新答案
                        break;      ///跳出此次枚举，因为已找到此次枚举的最小值
                    }
                }
                if(f(s)!=f(e))
                    break;
            }
            printf("%d\n",ans==INT_MAX?-1:ans);
        }
    }
    return 0;
}