首页 > 代码库 > HDU 1598 find the most comfortable road

HDU 1598 find the most comfortable road

对于中文题,直接讲思路吧!

思路:一看题目,兴奋啊,貌似是求最大流相关的问题,但是仔细审题一看,发现是要你去求最大速度与最小速度之差最小的路!最大最小之差最小,那么我们就可以联想到贪心的问题了,这题还有个地方在于能到达目的地,那么就是说明要连通给定的起点与终点了,所以我们可以考虑并查集的思想了!

所以本题的大致的思路可以确定为,我们可以对所有边的权值就行排序,然后从0开始对所有的点进行枚举,连通所有的点,看下find(a)是不是等于find(b),等于我们就可以进行拿此时的最大值与最小值作差就可以了!

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 100000000
int f[205],n;
struct p
{
    int u,v,w;
}num[1005];
bool cmp(p x,p y)
{
    return x.w<y.w;
}
int find(int x)
{
    if(x!=f[x])
        x=find(f[x]);
    return x;
}
int main()
{
    int m,t,i,j,k,minn;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        for(i=0;i<m;i++)
            scanf("%d %d %d",&num[i].u,&num[i].v,&num[i].w);
        sort(num,num+m,cmp);
        scanf("%d",&t);
        while(t--)
        {
            minn=inf;
            int a,b;
            scanf("%d %d",&a,&b);
            for(i=0;i<m;i++)//从第0个点开始进行枚举,找出所有的情况最优的解
            {
                for(k=1;k<=n;k++)   //每次枚举将确定一个新的并查集
                    f[k]=k;
                for(j=i;j<m;j++)    //从第i个点开始找出能连通x  y的路
                {
                    int x,y;
                    x=find(num[j].u);
                    y=find(num[j].v);
                    if(x!=y)
                        f[y]=x;
                    if(find(a)==find(b))
                    {
                        if(minn>num[j].w-num[i].w)
                            minn=num[j].w-num[i].w;
                        break;
                    }
                    if(j==m)    //第一次连通所有的点发现没有出现a 到  b 的路,那么我们就没必要再取找乐
                        break;
                }
            }
            if(minn==100000000)
                printf("-1\n");
            else
                printf("%d\n",minn);
        }
    }
    return 0;
}