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

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<n<=200)和m (m<=1000),表示有N个城市和M条SARS。
接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速为speedSARS。speed<=1000000
然后是一个正整数Q（Q<11),表示寻路的个数。
接下来Q行每行有2个正整数Start,End, 表示寻路的起终点。

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 val=1 

2-->3 val=2

3-->4 val=3

起点：2 终点：4

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

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

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=203;
const int INF=0x3f3f3f3f;
struct Eage{
	int from,to,val;
	friend bool operator<(const Eage&a,const Eage &b){
		return a.val<b.val;
	}
}a[maxn*maxn];
int fa[maxn];
int init(){
	for(int i=0;i<=maxn;i++)fa[i]=i;
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int Union(int a,int b){
	int p1=find(a),p2=find(b);
	fa[p2]=p1;
}
int n,m,q,st,ed;
int main(){
	while(cin>>n>>m){
		for(int i=0;i<m;i++){
			cin>>a[i].from>>a[i].to>>a[i].val;
		}
		sort(a,a+m);
		cin>>q;
		while(q--){
			cin>>st>>ed;
			int ans=INF;
			for(int i=0;i<m;i++){
				init();//枚举起点边
				for(int j=i;j<m;j++){
					Union(a[j].from,a[j].to);
					if(find(st)==find(ed)){
						ans=min(ans,a[j].val-a[i].val);break;
					}
				}
			}
			if(ans==INF)cout<<"-1"<<endl;
			else cout<<ans<<endl;
		}
	}
	return 0;
}