HDU 1598 find the most comfortable road （枚举+Kruskal）

HDU 1598 find the most comfortable road （枚举+Kruskal）2014-10-25 shuangde800 链接：

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

题目：

Problem DescriptionXX星有许多城市，城市之间通过一种奇怪的高速公路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 Input4 41 2 22 3 41 4 13 4 221 31 2Sample Output

10分析：

贪心的kruskal最小生成树算法思路，把路径按照从小到大排序，然后从小到大依次枚举“最小速度”，再寻找目标起点到目标终点的路径中的“最大速度”，为了使得它们的差更小，就要使得“最大速度”尽量的小。

本栏目更多精彩内容：http://www.bianceng.cn/Programming/sjjg/

那么为了让Start和End有路径，只需要按照kruskal算法从"最小路径"开始构造生成树，一旦发现Start和End有连接了，那么就表示已经构成满足条件的那个路径。由于路径已经排序好，那么此时所枚举“起点”和“满足条件之点”之差便是最大速度与最小速度之差。

代码：

#include<cstdio>#include<cstring>#include<algorithm>#define MAXN 210#define INF 2147483646using namespace std;int f[MAXN], rank[MAXN], n, m, pos;struct Edge{int u,v,val;friend bool operator<（const Edge&a,const Edge&b）{return a.val < b.val;}}arr[MAXN*MAXN];void init（）{for（int i=0; i<MAXN; ++i）f[i]=i,rank[i]=0;}int find（int x）{int i, j=x;while（j！=f[j]） j=f[j];while（x！=j）{i=f[x]; f[x]=j; x=i;}return j;}void Union（int x, int y）{int a=find（x）, b=find（y）;if（a==b）return;if（rank[a]>rank[b]）f[b]=a;else{if（rank[a]==rank[b]）++rank[b];f[a]=b;}}int main（）{int u,v,speed,Q;while（scanf（"%d%d",&n,&m）！=EOF）{for（int i=0; i<m; ++i）scanf（"%d%d%d",&arr[i].u,&arr[i].v,&arr[i].val）;sort（arr,arr+m）;scanf（"%d",&Q）;for（int i=0; i<Q; ++i）{scanf（"%d%d",&u,&v）;int ans=INF;for（int j=0; j<m; ++j）{init（）;for（int k=j; k<m; ++k）{Union（arr[k].u,arr[k].v）;if（find（u）==find（v））{ans = min（ans, arr[k].val-arr[j].val）;break;}}}if（ans==INF）printf（"-1
"）;else printf（"%d
",ans）;}}return 0;}