最小瓶頸路

說明：關于Uva的題目，可以在vjudge上做的，不用到Uva（那個極其慢的）網站去做。

最小瓶頸路：找u到v的一條路徑滿足最大邊權值盡量小

先求最小生成樹，然後u到v的路徑在樹上是唯一的，答案就是這條路徑。

Uva 534 Frogger

Time Limit: 3000MS 64bit IO Format: %lld & %llu

Description

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping. Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps. To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence. The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones. You are given the coordinates of Freddy’s stone, Fiona’s stone and all other stones in the lake. Your job is to compute the frog distance between Freddy’s and Fiona’s stone.

Input

The input file will contain one or more test cases. The first line of each test case will contain the number of stones n (2 ≤ n ≤ 200). The next n lines each contain two integers xi , yi (0 ≤ xi , yi ≤ 1000) representing the coordinates of stone #i. Stone #1 is Freddy’s stone, stone #2 is Fiona’s stone, the other n − 2 stones are unoccupied. There’s a blank line following each test case. Input is terminated by a value of zero (0) for n.

Output

For each test case, print a line saying ‘Scenario #x’ and a line saying ‘Frog Distance = y’ where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.

Sample Input

2

0 0

3 4

3

17 4

19 4

18 5

Sample Output

Scenario #1

Frog Distance = 5.000

Scenario #2

Frog Distance = 1.414

/*-------------------------------------------------*/
解析：      

原來的想法是先求最小生成樹，然後倍增求出答案。這樣雖然可以但是比較麻煩。對于要求U--V最小瓶頸路的總長度，這是最快的方法。 介于這道題是單對詢問路上最大邊的最小值，我們可以找到更簡單的做法：郭華陽在國家集訓隊論文裡介紹了最小生成樹的性質。就是在kruskal算法執行的時候第一次将兩個點（或者說兩個點的集合）連起來的那條邊就是這兩點的最小瓶頸路上最大邊。（因為kruskal是從小到大依次連邊的。）一旦明白了讓這條性質這題就變得簡單多了。

1 #include<iostream>
 2 using namespace std;
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 #define  N 205
 8 struct Edge{
 9     int u,v;
10     double w;
11 }edge[N*N];
12 int n,t;
13 struct D{
14     double x,y;
15 }dian[N];
16 int father[N];
17 void add_edge(int a,int b)
18 {
19     ++t;
20     edge[t].u=a;
21     edge[t].v=b;
22     edge[t].w=sqrt((dian[a].x-dian[b].x)*(dian[a].x-dian[b].x)+(dian[a].y-dian[b].y)*(dian[a].y-dian[b].y));
23 }
24 bool cmp(Edge P,Edge Q)
25 {
26     return P.w<Q.w;
27 }
28 int find(int x)
29 {
30     return (father[x]==x?x:father[x]=find(father[x]));
31 }
32 void kruskal(double &ans)
33 {
34     for(int i=1;i<=n;++i)
35       father[i]=i;
36     sort(edge+1,edge+t+1,cmp);
37     for(int l=1;l<=t;++l)
38     {
39         int f1=find(edge[l].u);
40         int f2=find(edge[l].v);
41         if(f1==f2) continue;
42         father[f2]=f1;
43         if(find(1)==find(2)) /*1是起點，2是終點，在kruskal算法執行的時候第一次将兩個點（或者說兩個點的集合）連起來的那條邊就是這兩點的最小瓶頸路上最大邊。*/
44         {
45             ans=edge[l].w;/*這個性質由kruskal算法的過程即可知道*/
46             return;
47         }
48     }
49 }
50 int main()
51 {
52     int topt=0;
53     while(scanf("%d",&n)==1)
54   {
55       topt++;
56       if(n==0) break;
57     t=0;
58     for(int i=1;i<=n;++i)
59     {
60         scanf("%lf%lf",&dian[i].x,&dian[i].y);
61         if(i==1)continue;
62         for(int j=1;j<i;++j)
63           add_edge(j,i);
64     }
65     double ans;
66     kruskal(ans);
67     printf("Scenario #%d\n",topt);
68     printf("Frog Distance = %0.3lf\n\n",ans);
69   }
70     return 0;
71 }