d946. D. 阿克圖洛斯‧蒙斯克的煩惱
http://zerojudge.tw/ShowProblem?problemid=d946
內容 ：
自從人類開始開發許多殖民行星，並和許多外星生物結下了樑子，各行星間的通訊管道已經變得日趨重要。當某個行星被攻打時，即可藉由通訊系統馬上呼叫鄰近行星的軍隊進行救援。
即使人類早已進軍太空多年，克卜魯星區的行星間通訊依然依靠著老式的無線電，在星區附近發生的超新星爆炸時常讓克卜魯星區的通訊系統部份斷線。這情形讓人類自治聯盟的最高統領阿克圖洛斯· 蒙斯克大帝非常地擔憂。如果在通訊系統剛好斷線時邊綠殖民地遭到外星族群攻擊將有可能讓他失去這些領土。
假設原本行星 A, B, C 之間互相是可以通訊的，現在行星 A 和 B 之間的無線電被超新星爆炸干擾而斷訊而 A — C 和 B — C 依然是可以通訊的，那我們說 A 和B 還是可以透過 C 行星互相通訊。
每兩個行星之間可擁有最多一個通訊頻道。每個通訊頻道都有一個通訊強度，代表這個頻道可以抵抗多大的干擾。每次的超新星爆炸都可以算出一個干擾值，星區中的所有通訊頻道都會受到一樣大的干擾，如果干擾值超過了或是剛好等於通訊強度，這個頻道就會斷線。
阿克圖洛斯‧蒙斯克授予你這項任務：給你克卜魯星區的通訊頻道概況，請你算出這個通訊網路能承受多大的超新星爆炸電磁干擾而不致於讓某些行星與主星克哈星失去聯絡。
輸入說明
：
輸入檔第一行為一個數字 T，代表總共有幾組測試資料。
每組測試資料以 1 ≤ N ≤ 100000 和 0 ≤ M ≤ 100000 開頭，N 代表克卜魯星區的行星數量，由 0 到 N - 1 編號，M 代表通訊頻道的數量。接下來 M 行用三個數字 Ai, Bi 和 Si 描述每一個頻道，代表 Ai 行星和 Bi 行星之間有一條強度為 Si 的頻道。其中 Ai 和 Bi 都是整數而 Si 是浮點數。
輸出說明
：
對於每一筆資料，輸出一個浮點數代表最少需要多大的干擾才能讓某些行星與克哈星 (行星編號 0) 失去聯絡。請將這個數字四捨五入到小數點以下第 4 位。
如果無法讓任何星球與克哈星失去聯絡，輸出 “No way.”。又假如某些星球在沒有干擾的狀況下就已經沒有音訊則輸出 “The empire of Arcturus is ending."。
範例輸入 ：
3 3 3 0 1 1.0 1 2 2.0 2 0 3.0 4 3 0 1 1.0 0 2 1.0 0 3 1.0 4 2 0 1 1.0 0 2 1.0
範例輸出 ：
2.0000 1.0000 The empire of Arcturus is ending.
提示
：
出處
：
作法 : 生成樹
將題目反過來想，將權值由大排到小
利用并查集，並將這些點互相連起來
直至所有點都在同一集合，也就是，一旦超過這個值
點之間必不連通!
/**********************************************************************************/
/* Problem: d946 "D. 阿克圖洛斯‧蒙斯克的煩惱" from 2010 NPSC 高中組初賽*/
/* Language: C */
/* Result: AC (756ms, 3140KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-20 15:16:15 */
/**********************************************************************************/
#include<stdio.h>
int Parent[100001], Rank[100001], total;
struct link {
int x, y;
float w;
}Data[100000], X[100000];
void Merge(int l, int m, int h) {
int In1 = l, In2 = m+1;
int a, b, Top = 0;
while(In1 <= m && In2 <= h) {
if(Data[In1].w > Data[In2].w) {
X[Top++] = Data[In1++];
}
else {
X[Top++] = Data[In2++];
}
}
while(In1 <= m) X[Top++] = Data[In1++];
while(In2 <= h) X[Top++] = Data[In2++];
for(a = 0, b = l; a < Top; a++, b++)
Data[b] = X[a];
}
void MergeSort(int l, int h) {
if(l < h) {
int m = (l+h)/2;
MergeSort(l, m);
MergeSort(m+1, h);
Merge(l, m, h);
}
}
void MakeSet(int N) {
int a;
for(a = 0; a <= N; a++)
Parent[a] = a, Rank[a] = 1;
}
int FindSet(int x) {
if(x != Parent[x])
Parent[x] = FindSet(Parent[x]);
return Parent[x];
}
void Link(int x, int y) {
if(Rank[x] > Rank[y])
Parent[y] = x, Rank[x] += Rank[y];
else
Parent[x] = y, Rank[y] += Rank[x];
}
void Union(int x, int y) {
x = FindSet(x), y = FindSet(y);
if(x != y)
Link(x, y), total++;
}
main() {
int T, n, m, a;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &n, &m);
for(a = 0; a < m; a++) {
scanf("%d %d %f", &Data[a].x, &Data[a].y, &Data[a].w);
}
if(n == 1) {puts("No way.");continue;}
MakeSet(n);
MergeSort(0, m-1);
for(a = 0, total = 0; a < m; a++) {
Union(Data[a].x, Data[a].y);
if(total == n-1) break;
}
if(total == n-1)
printf("%.4f\n", Data[a].w);
else
puts("The empire of Arcturus is ending.");
}
return 0;
}
上一篇：b090. D. 正直DE