1001 舒適的路線

NOIP 2006

時間限制: 2 s 空間限制: 128000 KB 題目等級 : 鉆石 Diamond 題目描述 Description

Z小鎮是一個景色宜人的地方，吸引來自各地的觀光客來此旅游觀光。
Z小鎮附近共有
N(1<N≤500)個景點（編號為1,2,3,…,N），這些景點被M（0<M≤5000）條道路連接著，所有道路都是雙向的，兩個景點之間可能有多條道路。也許是為了保護該地的旅游資源，Z小鎮有個奇怪的規定，就是對于一條給定的公路Ri，任何在該公路上行駛的車輛速度必須為Vi。頻繁的改變速度使得游客們很不舒服，因此大家從一個景點前往另一個景點的時候，都希望選擇行使過程中最大速度和最小速度的比盡可能小的路線，也就是所謂最舒適的路線。

?

輸入描述 Input Description

第一行包含兩個正整數，N和M。
接下來的M行每行包含三個正整數：x，y和v（1≤x,y≤N，0 最后一行包含兩個正整數s，t，表示想知道從景點s到景點t最大最小速度比最小的路徑。s和t不可能相同。

?

輸出描述 Output Description

如果景點s到景點t沒有路徑，輸出“IMPOSSIBLE”。否則輸出一個數，表示最小的速度比。如果需要，輸出一個既約分數。

?

樣例輸入 Sample Input

樣例1
4 2
1 2 1
3 4 2
1 4

樣例2
3 3
1 2 10
1 2 5
2 3 8
1 3

樣例3
3 2
1 2 2
2 3 4
1 3

?

樣例輸出 Sample Output

樣例1
IMPOSSIBLE

樣例2
5/4

樣例3
2

?

數據范圍及提示 Data Size & Hint

N(1<N≤500)

M（0<M≤5000）

Vi在int范圍內

?

分析 Analysis

這道題解法最小生成樹（雖然標了并查集的Tag）

解法不難，但是有點難想。我們需要一條速度變化最小的路徑，那么可以把邊按邊權排序，因此邊權相近的邊會放在一起，顯然一棵生成樹可以滿足我們的需求。

那么我們枚舉最大邊，在生成生成樹的過程中，只要s和t相連了就可以立刻退出，在這之前維護一個最小邊，退出前更新答案。

?

代碼 Code

1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #define maxn 1000000 6 using namespace std; 7 8 struct edge{ 9 int u,v,len; 10 }e[maxn]; 11 12 bool cmp(const edge &a,const edge &b){ 13 return a.len < b.len; 14 } 15 16 int gcd(int a,int b){ 17 return (!b)?a:gcd(b,a%b); 18 } 19 20 int pre[maxn],n,m,s,t; 21 int find(int x){ 22 if(!pre[x]) return x; 23 else{ 24 pre[x] = find(pre[x]); 25 return pre[x]; 26 } 27 } 28 void unite(int u,int v){ 29 if(find(u) != find(v)){ 30 pre[find(u)] = find(v); 31 } 32 } 33 void kruskal(){ 34 sort(e,e+m,cmp); 35 36 int gua = 999999999,a,b; 37 bool swi = false; 38 int p = m-1; 39 40 for(p = m-1;p >= 0;p--){ 41 memset(pre,0,sizeof(pre)); 42 int maxx = -999999999; 43 int minn = 999999999; 44 swi = false; 45 for(int i = p;i >= 0;i--){ 46 int u = e[i].u,v = e[i].v; 47 if(find(u) != find(v)){ 48 unite(u,v); 49 maxx = max(e[i].len,maxx); 50 minn = min(e[i].len,minn); 51 } 52 53 if(find(s) == find(t)){ 54 swi = true; 55 break; 56 } 57 } 58 59 if(!swi) break; 60 if(maxx-minn < gua){ 61 gua = maxx-minn,a = maxx,b = minn; 62 } 63 // if(1.0*maxx/minn > 0) ans = min(ans,1.0*maxx/minn); 64 } 65 66 67 if(!swi && p == m-1) printf("IMPOSSIBLE"); 68 else if(a%b == 0) printf("%d",a/b); 69 else printf("%d/%d",a/gcd(a,b),b/gcd(a,b)); 70 71 // printf("\n%d",p); 72 } 73 74 int main(){ 75 scanf("%d%d",&n,&m); 76 77 for(int i = 0;i < m;i++){ 78 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].len); 79 } 80 81 scanf("%d%d",&s,&t); 82 83 kruskal(); 84 85 return 0; 86 } 深夜打代碼= =

?

轉載于:https://www.cnblogs.com/Chorolop/p/7407500.html

總結

以上是生活随笔為你收集整理的[Codevs] 1001 舒适的路线的全部內容，希望文章能夠幫你解決所遇到的問題。

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