题意：在一张图上有若干点，告诉你每个点的坐标，然后问你从a到b的最小瓶颈路。最小瓶颈路就是找到一条路径上面最大的边最小。
思路：原来的想法是先求最小生成树，然后倍增求出答案。这样虽然可以但是比较麻烦，介于这道题是单对询问我们可以找到更简单的做法，郭华阳在国家集训队论文里介绍了最小生成树的性质。就是在kruskal算法执行的时候第一次将两个点连起来的那条边就是最小瓶颈路。一旦明白了让这条性质这题就变得简单多了。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstring> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #include <set> 11 #include <map> 12 #define MP(a, b) make_pair(a, b) 13 #define PB(a) push_back(a) 14 15 using namespace std; 16 17 typedef long long ll; 18 typedef pair<int ,int> pii; 19 typedef pair<unsigned int, unsigned int> puu; 20 typedef pair<int ,double> pid; 21 typedef pair<ll, int> pli; 22 typedef pair<double, double> Point; 23 24 const int INF = 0x3f3f3f3f; 25 const double eps = 1e-6; 26 const int LEN = 510; 27 Point p[LEN]; 28 struct edge{ int from, to;double val; }; 29 edge e[LEN*LEN]; 30 //两点距离 31 inline double dis(Point a, Point b){return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));} 32 inline bool cmp(edge a, edge b){return a.val<b.val;} //边比较函数权值小的在前面 33 edge ME(int a, int b, double c){edge ret;ret.from=a;ret.to=b;ret.val=c;return ret;} //返回一条边 34 //UFSET 35 int parent[LEN], kase = 1, n; 36 void init(){for(int i=0; i<n; i++)parent[i] = i;} 37 int Find(int a){return parent[a]==a?a:Find(parent[a]);} 38 39 int main() 40 { 41 // freopen("in.txt", "r", stdin); 42 43 int top, x, y; 44 while(scanf("%d", &n)!=EOF && n){ 45 for(int i=0; i<n; i++) scanf("%lf%lf", &p[i].first, &p[i].second); 46 top = 0; 47 for(int i=0; i<n; i++) 48 for(int j=0; j<i; j++) 49 e[top++] = ME(i, j, dis(p[i],p[j])); 50 sort(e, e+top, cmp); 51 init(); 52 printf("Scenario #%d\n", kase++); 53 for(int i=0; i<top; i++){ 54 x = e[i].from; y = e[i].to; 55 x = Find(x);y = Find(y); 56 if(x==y)continue; 57 parent[x] = y; 58 if(Find(0)==Find(1)){ 59 printf("Frog Distance = %.3lf\n\n", e[i].val); 60 break; 61 } 62 } 63 } 64 return 0; 65 }