NYOJ 711 最舒适的路线（并查集）
生活随笔
收集整理的這篇文章主要介紹了
NYOJ 711 最舒适的路线（并查集）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
最舒適的路線
時間限制：5000?ms ?|? 內存限制：65535?KB 難度：5描述
異形卵潛伏在某區域的一個神經網絡中。其網絡共有N個神經元（編號為1,2,3,…,N），這些神經元由M條通道連接著。兩個神經元之間可能有多條通道。異形卵可以在這些通道上來回游動，但在神經網絡中任一條通道的游動速度必須是一定的。當然異形卵不希望從一條通道游動到另一條通道速度變化太大，否則它會很不舒服。
現在異形卵聚居在神經元S點，想游動到神經元T點。它希望選擇一條游動過程中通道最大速度與最小速度比盡可能小的路線，也就是所謂最舒適的路線。
輸入接下來對每組測試數據：
第1行: N M
第2~M+1行： Xi Yi Vi (i=1,…..,M)
表示神經元Xi 到神經元Yi之間通道的速度必須是Vi
最后一行： S T ( S ? T )
【約束條件】
2≤K≤5 1<N≤500 0<M≤5000 1≤ Xi, Yi , S , T ≤N 0< Vi <30000，
Vi是整數。數據之間有一個空格。
分析：枚舉速度最大的邊，找出能夠從S到達T的最大速度，然后求出它們的比值，與已經求出的比值進行比較，如果比之前的比值小，則更新比值，記錄此種情況下的最大速度和最小速度，直到枚舉到從S不能到達T，跳出循環。求出最大速度和最小速度的比值即可。如果從S可以到達T，說明S和T屬于同一個集合，因此可以利用并查集來判斷從S是否可以到達T。
#include<stdio.h> #include<algorithm> #define INF 0x3fffffff using namespace std;const int N = 5005; struct edge {int x;int y;int v; }e[N]; int father[N];void Init(int n) {for(int i = 1; i <= n; i++)father[i] = i; }bool comp(edge e1, edge e2) {return e1.v > e2.v; }int Find(int x) {if(x != father[x])father[x] = Find(father[x]);return father[x]; }void Union(int a, int b) {int p = Find(a);int q = Find(b);if(p > q)father[p] = q;elsefather[q] = p; }int gcd(int a, int b) {while(b != 0){int r = a % b;a = b;b = r;}return a; }int main() {int T, n, m, i, j, s, t, aa, bb;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(i = 0; i < m; i++)scanf("%d%d%d",&e[i].x, &e[i].y, &e[i].v);scanf("%d%d",&s,&t);sort(e, e+m, comp);double rate = INF*1.0;for(i = 0; i < m; i++) //枚舉速度最大的邊{Init(n);for(j = i; j < m; j++) //查找使S到達T的最大速度{if(Find(e[j].x) != Find(e[j].y))Union(e[j].x, e[j].y);if(Find(s) == Find(t))break;}if(j == m) break;int v1 = e[i].v, v2 = e[j].v;if(v1*1.0 / v2 < rate) //比原來的比值小{aa = v1, bb = v2; //記錄最大速度和最小速度rate = v1*1.0 / v2; //更新最小比值}}if(rate == INF)printf("IMPOSSIBLE\n");else if(aa % bb == 0)printf("%d\n",aa/bb);elseprintf("%d/%d\n",aa/gcd(aa,bb), bb/gcd(aa,bb));}return 0; }
總結
以上是生活随笔為你收集整理的NYOJ 711 最舒适的路线（并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 谈谈双亲委派模型的第四次破坏-模块化
- 下一篇： NYOJ 248 BUYING FEE