hdu1598Kruscal+枚举

http:acm.hdu.edu.cnshowproblem.php?pid1598findthemostcomfortableroadTimeLimit:10001000MS(J

 

http://acm.hdu.edu.cn/showproblem.php?pid1598

find the most comfortable road

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10307    Accepted Submission(s): 4289  

Problem Description

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

Input

输入包括多个测试实例每个实例包括 第一行有2个正整数n (1

Output

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

Sample Input

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

Sample Output

1

0

思路

这里我们应用了Kruscal的思想

我们都知道Kruscal是把边权排序然后从小到大依次并查集加边判环最终形成最小生成树的

而这个题呢  因为要求的是一条路径的最大速度和最小速度之差

如果你朴素做法的话DFS找一条路并且记忆化搜索拿到最大速度and最小速度。

这样找下来虽然这个图不大但找出所有路并计算复杂度也太高了。

我们换一种想法边权就是速度按照Krusal的思想把边权排序依次加边

这样的话集合里的边最大速度和最小速度就是第一个加进去的和最后一个加进去的

每次加边的时候通过并查集判断起点和终点是否联通若联通了就直接ans最大速度减去最小速度

但是这样做还有一个问题

比如  这样

1-->2 val1 

2-->3 val2

3-->4 val3

起点2 终点4

按照我们的思路肯定是依次这三条边依次加进去但是第三次我们才会判断到2和4联通了但是我们记录的最小值却是1-->2的val我们的ans3-12起点边错了导致答案错了。但是终点边是不会错的一定会是我们需要的最大速度。

所以我们需要再外边再套一层循环枚举起点边就好了。

代码

#include#include#include#includeusing namespace std;typedef long long ll;const int maxn203;const int INF0x3f3f3f3f;struct Eage{int from,to,val;friend bool operator<(const Eage}}a[maxn*maxn];int fa[maxn];int init(){for(int i0;i>n>>m){for(int i0;i>a[i].from>>a[i].to>>a[i].val;}sort(a,am);cin>>q;while(q--){cin>>st>>ed;int ansINF;for(int i0;i