nyoj 711最舒適的路線(第六屆河南省程序設計大賽 並查集)

最舒適的路線

描述

異形卵潛伏在某區域的一個神經網絡中。其網絡共有N個神經元（編號為1,2,3,…,N），這些神經元由M條通道連接著。兩個神經元之間可能有多條通道。異形卵可以在這些通道上來回游動，但在神經網絡中任一條通道的游動速度必須是一定的。當然異形卵不希望從一條通道游動到另一條通道速度變化太大，否則它會很不舒服。

現在異形卵聚居在神經元S點，想游動到神經元T點。它希望選擇一條游動過程中通道最大速度與最小速度比盡可能小的路線，也就是所謂最舒適的路線。

輸入第一行： K 表示有多少組測試數據。
接下來對每組測試數據：
第1行: N M
第2~M+1行： Xi Yi Vi (i=1,…..,M)
表示神經元Xi 到神經元Yi之間通道的速度必須是Vi
最後一行： S T ( S  T )

【約束條件】
2≤K≤5 1 Vi是整數。數據之間有一個空格。

輸出對於每組測試數據，輸出一行：如果神經元S到神經元T沒有路線，輸出“IMPOSSIBLE”。否則輸出一個數，表示最小的速度比。如果需要，輸出一個既約分數。

樣例輸入

2
3 2
1 2 2
2 3 4
1 3
3 3
1 2 10
1 2 5
2 3 8
1 3

樣例輸出

2

5/4

來源第六屆河南省程序設計大賽

上傳者ACM_趙銘浩

剛開始看這道題 想著用深搜吧 因為看到時間5000ms 結果發現越來越寫不下去

因為這道題有重邊啊 而且重邊還不能去掉 都要考慮 唉 我的想法至此打住

確確實實發現自己總喜歡深搜了。。。唉 時間是個硬傷啊

苦思冥想 想到了度娘 哈哈

題解：

首先對速度排序 在這裡從大到小。使用並查集，然後從下標0開始遍歷，直到s 和t在一個集合裡面

這個時候再判斷最大速度和最小速度比值和rate比較。我當初看的時候想了想為什麼這樣遍歷的結果一定是正確的呢

仔細想了想 由於我們對速度排序了 我們當前判斷的s和t在一個集合裡面的所有邊一定是最大速度/最小速度 最小的值

為什麼呢？我們可以再做個假設，如果當前集合最小速度的邊還有一個更小的速度 如果我們使用這個更小的速度 最大速度/最小速度<最大速度/更小速度 懂了嗎?

ac代碼:

#include 
#include 
#include 
using namespace std;
struct node
{
	int a,b;
	int speed;
}c[5005];
int fa[505];
bool cmp(node x,node y)
{
	return x.speed>y.speed;
}
void init(int n)
{
	for(int i=0;i<=n;i++)
	fa[i]=i;
}
int find(int x)
{
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
int gcd(int a,int b)
{
	int r;
	while(b)
	r=a%b,a=b,b=r;
	return a;
}
int main()
{
	int ncase;
	scanf("%d",&ncase);
	while(ncase--)
	{
		int n,m;
		memset(&c,0,sizeof(&c));
		scanf("%d %d",&n,&m);
		for(int i=0;i