hdu1598-----Kruscal+枚举
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;
}