题目链接
【题意】
平面直角坐标系上给定n个点，求前两个点的最小瓶颈路的大小，最小瓶颈路是指无向图中有两个结点u,v，求出从u到v的一条路径，使得这条路径上的最长的边尽可能的短，这条最长的边长就是答案。【思路】
这道题目有两种做法，因为只问前两个点的最小瓶颈路，所以可以直接用kruscal算法做，这里有一个重要的结论就是kruscal算法执行的时候第一次将结点u,v连通起来时，那么这条边就是u,v之间的最小瓶颈路，根据这个结论，在kruscal算法每次加边的时候判断前两个结点是否连通，连通则立刻输出这条边的边长即可。#includeusing namespace std;const int maxn = 220;struct Edge { int from, to; double dist; Edge(int f = 0, int t = 0, double d = 0) :from(f), to(t), dist(d) {} bool operator<(const Edge& e) const { return dist < e.dist; }};int n;int par[maxn];int x[maxn], y[maxn];vector edges;double dis(int x1, int y1, int x2, int y2) { return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));}int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }void kruscal() { for (int i = 0; i < n; ++i) par[i] = i; for (int i = 0; i < edges.size(); ++i) { int x = find(edges[i].from); int y = find(edges[i].to); if (x != y) { par[x] = y; } if (find(0) == find(1)) { printf("Frog Distance = %.3lf\n\n", edges[i].dist); return; } }}int main() { int kase = 0; while (scanf("%d", &n) == 1 && n) { for (int i = 0; i < n; ++i) { scanf("%d%d", &x[i], &y[i]); } edges.clear(); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { double d = dis(x[i], y[i], x[j], y[j]); edges.push_back(Edge(i, j, d)); } } sort(edges.begin(), edges.end()); printf("Scenario #%d\n", ++kase); kruscal(); } return 0;}
这道题的数据规模较小，所以我们也可以求出整个图任意两点的最小瓶颈路，方法就是大白书343页所讲，设f(u,v)是u,v之间的最小瓶颈路，那么在求出最小生成树并建立好无向图之后，可以借助于dfs求解，设u是当前dfs访问的结点，dfs下一次访问的结点是v，每次dfs要更新v和所有的已访问结点x的最小瓶颈路f[v][x]和f[x][v]，那么f[v][x]=f[x][v]=max(f[x][u],w(u,v))，u相当于v的父亲结点。
#includeusing namespace std;const int maxn = 220;struct Edge { int from, to; double dist; Edge(int f = 0, int t = 0, double d = 0.0) :from(f), to(t), dist(d) {} bool operator<(const Edge& e) const { return dist < e.dist; }};int n;int par[maxn];int x[maxn], y[maxn];double f[maxn][maxn];//f[u][v]=f[v][u]=u,v两点之间的最小瓶颈路bool used[maxn];vector edges, g[maxn];//g是邻接表double dis(int x1, int y1, int x2, int y2) { return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));}int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }void kruscal() { int cnt = 0; for (int i = 0; i < n; ++i) { par[i] = i; g[i].clear(); } for (int i = 0; i < edges.size(); ++i) { int x = find(edges[i].from); int y = find(edges[i].to); if (x != y) { par[x] = y; //建立无向图 g[edges[i].from].push_back(Edge(edges[i].from, edges[i].to, edges[i].dist)); g[edges[i].to].push_back(Edge(edges[i].to, edges[i].from, edges[i].dist)); if (++cnt == n - 1) return; } }}void dfs(int u) { used[u] = 1; for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i].to;//v是u的子结点 double d = g[u][i].dist; if (!used[v]) { for (int x = 0; x < n; ++x) { if (used[x])//遍历所有已访问结点 f[x][v] = f[v][x] = max(f[u][x], d);//更新答案 } dfs(v); } }}int main() { int kase = 0; while (scanf("%d", &n) == 1 && n) { for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]); edges.clear(); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { double d = dis(x[i], y[i], x[j], y[j]); edges.push_back(Edge(i, j, d)); } } sort(edges.begin(), edges.end()); kruscal(); memset(used, 0, sizeof(used)); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) f[i][j] = 0.0; dfs(0); printf("Scenario #%d\nFrog Distance = %.3lf\n\n", ++kase, f[0][1]); } return 0;}