find the most comfortable road
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7532 Accepted Submission(s):
3175
Problem Description
XX星有许多城市,城市之间通过一种奇怪的高速公路SARS(Super Air Roam
Structure---超级空中漫游结构)进行交流,每条SARS都对行驶在上面的Flycar限制了固定的Speed,同时XX星人对
Flycar的“舒适度”有特殊要求,即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求,flycar必须瞬间提速/降速,痛苦呀
),
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的)。
但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, 表示寻路的起终点。
第一行有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
题目是这样。因为要使找到的路的舒适度值最大,所以经过的路线中,最大和最小的速度之差应该越小越好。所以依照这种原则,先把所有的边按照速度大小从小到大排序(亦可从大到小),这样按顺序来扫。每扫一条边判断一下起始点和终止点是否联通(这里用到并查集)。这样一来,两点一旦联通,立刻跳出循环,就可以使这条路线的舒适度相应局部的最大。再通过改变开始扫描边的位置来把局部解变成全局解。
私以为其实和最小生成树没多大关系,看题解的时候也是闹心半天。可以把这个看作生成树的一个变形,只是没有严格按照连接点的顺序来生成,是按照边的大小顺序来生成,会让人难懂一些。另外并查集这东西很简单,没听过可以去这里看一下:http://www.cnblogs.com/cyjb/p/UnionFindSets.html
前一阵子期末复习阶段太忙(懒)以至于没有更新(呵呵呵说得好像很多人看一样)。这个博客本来也没什么人,就当做提升自己的一个地方吧。不过能帮到别人那也是再好不过了~~
代码贴下:
#include<iostream> #include<cstdio> #include<string.h> #include<algorithm> using namespace std; class bian { public: int s,e,p; bool operator<(const bian &a)const { return p<a.p; } }; bian a[1010]; int fa[210]; void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; } int findset(int i) { if(fa[i]==i) return i; else return findset(fa[i]); } int main() { int n,m,q; while(~scanf("%d%d",&n,&m)) { memset(a,0,sizeof(a)); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].p); } sort(a+1,a+m+1); scanf("%d",&q); while(q--) { int a1,b1; scanf("%d%d",&a1,&b1); int minn=0x3f3f3f3f; for(int i=1;i<=m;i++) { // cout << "a" << i << ": " << a[i].s << a[i].e << a[i].p << endl; init(n); for(int j=i;j<=m;j++) { int fs=findset(a[j].s),fe=findset(a[j].e); if(fs!=fe) { fa[fs]=fe; } if(findset(a1)==findset(b1)) { minn=min(minn,a[j].p-a[i].p); break; } } } if(minn!=0x3f3f3f3f) printf("%d ",minn); else printf("-1 "); } } return 0; }