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

思路：并查集+貪心+kruskal，將路徑升序排序， 然后依次枚舉最小速度， 再尋找目標起點到目標終點的路徑中的最大速度，為了使差更小，就要使最大速度盡量的小，按照kruskal算法從最小路徑開始構造生成樹，直到所連出的樹含有起點和終點為止。

Source Program

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #define INF 999999 #define N 201 #define MOD 1000000007 #define E 1e-12 using namespace std; struct Node {int x;int y;int w; }a[5*N]; int n,m; int father[N]; int Find(int x) {int r=x;while(r!=father[r])r=father[r];int i=x,j;while(i!=r){j=father[i];father[i]=r;i=j;}return r; } bool cmp(Node a,Node b) {return a.w<b.w; } int main() {while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);sort(a,a+m,cmp);int t;scanf("%d",&t);for(int i=0;i<t;i++){int s,e;scanf("%d%d",&s,&e);int MST=INF;for(int j=0;j<m;j++){for(int i=1;i<=n;i++)father[i]=i;for(int k=j;k<m;k++){int x=Find(a[k].x);int y=Find(a[k].y);if(x!=y)father[x]=y;if(Find(s)==Find(e)){MST=min(MST,a[k].w-a[j].w);break;}}}if(MST!=INF)printf("%d\n",MST);elseprintf("-1\n");}}return 0; }

?

總結

以上是生活随笔為你收集整理的Find the most comfortable road（HDU-1598）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。