hdu1598 最小內插補點生成樹

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，而按最小生成樹，其內插補點是1。

是以最小內插補點生成樹到底咋求？

注意到資料範圍，複雜度可能是 O ( q ∗ m 2 ) O(q*m^2) O(q∗m2)，我們可以枚舉生成樹的最小邊 j j j ，再生成一顆樹。

而這棵樹就是在以 j j j 為最小邊的最小內插補點生成樹。證明方法和克魯斯卡爾很相似。假如有更小的最大邊，那麼加上它之後會形成一個環，而它比最大邊要小，我們在枚舉到它這條邊的時候（這時候還沒有枚舉到最大邊）顯然就會把它連通。而事實上我們并沒有把它連通，是以不存在更小的最大邊。

代碼如下

#include <bits/stdc++.h>
#define inf 2147483647
using namespace std;
struct node{
	int a, b, c;
	bool operator < (const node & A) const{
		return c < A.c;
	}
}d[1005];
int f[205];
int find(int x){
	return x == f[x]? x: f[x] = find(f[x]);
}
int main(){
	int i, j, n, m, q, u, v, a, b, c, ans;
	while(scanf("%d%d", &n, &m) != EOF){
		for(i = 1; i <= m; i++) scanf("%d%d%d", &d[i].a, &d[i].b, &d[i].c);
		sort(d + 1, d + i);
		scanf("%d", &q);
		while(q--){
			ans = inf;
			scanf("%d%d", &u, &v);
			for(i = 1; i <= m; i++){
				for(j = 1; j <= n; j++) f[j] = j;
				for(j = i; j <= m; j++){
					a = find(d[j].a); b = find(d[j].b);
					if(a != b) f[a] = b;
					if(find(u) == find(v)){
						ans = min(ans, d[j].c - d[i].c);
						break;
					}
				}
			}
			if(ans < inf) printf("%d\n", ans);
			else printf("-1\n");
		}
	}
	return 0;
}