首页 > ACM题库 > HDU-杭电 > HDU 1598 find the most comfortable road-并查集-[解题报告] C++
2013
12-12

HDU 1598 find the most comfortable road-并查集-[解题报告] C++

find the most comfortable road

问题描述 :

XX星有许多城市,城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure—超级空中漫游结构)进行交流,每条SARS都对行驶在上面的Flycar限制了固定的Speed,同时XX星人对 Flycar的“舒适度”有特殊要求,即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求,flycar必须瞬间提速/降速,痛苦呀 ),
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的)。

输入:

输入包括多个测试实例,每个实例包括:
第一行有2个正整数n (1<n<=200)和m (m<=1000),表示有N个城市和M条SARS。
接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速为speedSARS。speed<=1000000
然后是一个正整数Q(Q<11),表示寻路的个数。
接下来Q行每行有2个正整数Start,End, 表示寻路的起终点。

输出:

每个寻路要求打印一行,仅输出一个非负整数表示最佳路线的舒适度最高速与最低速的差。如果起点和终点不能到达,那么输出-1。

样例输入:

4 4
1 2 2
2 3 4
1 4 1
3 4 2
2
1 3
1 2

样例输出:

1
0

http://acm.hdu.edu.cn/showproblem.php?pid=1598

才开始是我看着没什么思路,心想就用dfs暴搜试试吧(本人太爱dfs了)。结果加了各种剪枝都都是TLE无语。。最后听von说用并查集,给我讲了讲才明白,不过开始的时候把边的最大值开成点的最大值了贡献了4次wa才检查出来。。无语了,自己太马虎了。。

思路:先将各个边按限速排序,然后从最大的开始里循环用并查集建树,直到起点与终点的父亲相同说明此事s与e已经建立联系,然后用开始循环的节点的速度(该路线上的最大速速)减去最后将s,e连接的边的速度就是该路径上的Vmax-Vmin的最小了。。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int max_s = 1007;
int f[207];
struct node
{
    int a,b,w;
}p[max_s];
int n;
int cmp(const void *a,const void *b)
{
    return (*(node*)b).w-(*(node*)a).w;
}
void init()
{
    for(int i=0;i<=n;i++)
    f[i]=i;
}
int find(int a)
{
    if(f[a]!=a)
    f[a]=find(f[a]);
    return f[a];
}
void Union(int a,int b)
{
    int x=find(a);
    int y=find(b);
    if(x!=y)
    f[y]=x;
}

int main()
{
    //freopen("d.txt","r",stdin);
    int m,i,j,op;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=0;i<m;i++)
        scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].w);
        qsort(p,m,sizeof(p[0]),cmp);
        scanf("%d",&op);
        while(op--)
        {
            int s,e;
            scanf("%d%d",&s,&e);
            int min=9999999;
            for(i=0;i<m;i++)
            {
                init();
                for(j=i;j<m;j++)
                {
                    Union(p[j].a,p[j].b);
                    if(find(s)==find(e))
                    {
                        if(min>p[i].w-p[j].w)
                        min=p[i].w-p[j].w;
                        break;
                    }
                }
            }
            if(min!=9999999)
            printf("%d\n",min);
            else
            printf("-1\n");
        }
    }
    return 0;
}

解题报告转自:http://www.cnblogs.com/E-star/archive/2011/11/23/2261045.html


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确