该题就是求一只青蛙从1号石头跳到2号石头的所有路径中跳跃距离最大值的最小值。仔细想想的话，将原来dijkstra的dis数组赋值为这个minmax含义，同样满足贪心规则，所以就是普通的dijkstra。
代码如下：
#include#include #include #include #include #define MAXN 205using namespace std;int N;struct Node{ int x, y;}e[MAXN];double G[MAXN][MAXN], dis[MAXN]; // 定义dis数组用来保留minmax值,且该值满足贪心规则int hash[MAXN];inline double dist(int x, int y){ return sqrt(double((e[x].x-e[y].x)*(e[x].x-e[y].x)+(e[x].y-e[y].y)*(e[x].y-e[y].y)));} double dijkstra(){ int pos; double Min; fill(dis, dis+MAXN, 9999999999.); memset(hash, 0, sizeof (hash)); dis[1] = 0; // 到达第一号石头所需要的mm值为0 hash[1] = 1; for (int i = 1; i <= N; ++i) { pos = 1, Min = 9999999999.; for (int j = 1; j <= N; ++j) { if (!hash[j] && Min - dis[j] > 1e-6) { pos = j; Min = dis[j]; } } hash[pos] = 1; if (pos == 2) { return dis[2]; } for (int j = 1; j <= N; ++j) { double t = max(dis[pos], G[pos][j]); if (!hash[j]) { dis[j] = min(dis[j], t); } } }}int main(){ int ca = 0; while (scanf("%d", &N), N) { memset(G, 0, sizeof (G)); for (int i = 1; i <= N; ++i) { scanf("%d %d", &e[i].x, &e[i].y); } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { G[i][j] = dist(i, j); } } printf("Scenario #%d\n", ++ca); printf("Frog Distance = %.3lf\n\n", dijkstra()); } return 0;}
kruskal版本
#include#include #include #include #include #define MAXN 205using namespace std;int N, pos, set[MAXN];struct Node{ int x, y; double far; bool operator < (Node t) const { return far < t.far; }}e[40005];struct { int x, y;}p[205];inline double dist(int x, int y){ return sqrt(double((p[x].x-p[y].x)*(p[x].x-p[y].x) + (p[x].y-p[y].y)*(p[x].y-p[y].y)));}int find(int x){ return set[x] = set[x] == x ? x : find(set[x]);}inline void merge(int a, int b){ set[a] = b;}int main(){ int ca = 0; while (scanf("%d", &N), N) { pos = 0; for (int i = 1; i <= N; ++i) { scanf("%d %d", &p[i].x, &p[i].y); set[i] = i; } for (int i = 1; i <= N; ++i) { for (int j = i+1; j <= N; ++j) { ++pos; e[pos].x = i, e[pos].y = j; ++pos; e[pos].x = j, e[pos].y = i; e[pos].far = e[pos-1].far = dist(i, j); } } sort(e+1, e+1+pos); for (int i = 1; i <= pos; ++i) { int a = find(e[i].x), b = find(e[i].y); if (a != b) { merge(a, b); } if (find(1) == find(2)) { printf("Scenario #%d\n", ++ca); printf("Frog Distance = %.3lf\n\n", e[i].far); break; } } } return 0;}
dfs版本
#include#include #include #include #include #define MAXN 205#define INF 29999999.using namespace std;int N, head[MAXN], pos;double dis[MAXN];struct { int x, y;}p[205];struct edge{ int num, next; double far;}e[40005];inline double dist(int x, int y){ return sqrt(double((p[x].x-p[y].x)*(p[x].x-p[y].x) + (p[x].y-p[y].y)*(p[x].y-p[y].y)));}void insert(int x, int y){ ++pos; e[pos].next = head[x]; e[pos].num = y; e[pos].far = dist(x, y); head[x] = pos;}void dfs(int x, double far){ if (x == 2) { return; } for (int i = head[x]; i; i = e[i].next) { double t = max(e[i].far, far); if (dis[e[i].num]-t > 1e-6) { dis[e[i].num] = t; dfs(e[i].num, dis[e[i].num]); } }}int main(){ int ca = 0; while (scanf("%d", &N), N) { pos = 0; fill(dis, dis+MAXN, INF); memset(head, 0, sizeof (head)); for (int i = 1; i <= N; ++i) { scanf("%d %d", &p[i].x, &p[i].y); } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { insert(i, j); } } dis[1] = 0.; dfs(1, dis[1]); printf("Scenario #%d\n", ++ca); printf("Frog Distance = %.3lf\n\n", dis[2]); } return 0;}
Floyd版本
#include#include #include #include #include #include using std::max;using std::min;using std::cin;using std::cout;using std::endl;int N;struct Node { int x, y;}e[205];double G[205][205];double dist(const Node & a, const Node & b) { return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); }void build() { for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { G[i][j] = dist(e[i], e[j]); } } }void floyd() { for (int k = 1; k <= N; ++k) { for (int i = 1; i <= N; ++i) { if (i == k) continue; for (int j = 1; j <= N; ++j) { if (G[i][k] > G[i][j] || G[k][j] > G[i][j] || j == k) continue; G[i][j] = min(G[i][j], max(G[i][k], G[k][j])); } } } }int main () { int ca = 0; while (cin >> N, N) { for (int i = 1; i <= N; ++i) { cin >> e[i].x >> e[i].y; } build(); floyd(); printf("Scenario #%d\n", ++ca); printf("Frog Distance = %.3f\n\n", G[1][2]); } return 0;}
SPFA版本
#include#include #include #include #include #include #define INF 999999999.#define MAXN 205using namespace std;// 该题每两点之间都有边的存在，所以这里用SPFA遍历边的时候并没有什么优势int N, head[MAXN], pos;double dis[MAXN];struct Node{ int x, y;}e[MAXN];struct Edge{ int num, next; double far;}edge[40005];double dist(int x, int y){ return sqrt(double((e[x].x-e[y].x)*(e[x].x-e[y].x)+(e[x].y-e[y].y)*(e[x].y-e[y].y)));}void insert(int x, int y){ ++pos; edge[pos].next = head[x]; edge[pos].num = y; edge[pos].far = dist(x, y); head[x] = pos;}double SPFA(){ int obj; queue q; fill(dis, dis+MAXN, INF); dis[1] = 0; q.push(1); while (!q.empty()) { obj = q.front(); q.pop(); for (int i = head[obj]; i; i = edge[i].next) { double t = max(dis[obj], edge[i].far); if (t < dis[edge[i].num]) { dis[edge[i].num] = t; q.push(edge[i].num); } } } return dis[2];}int main(){ int ca = 0; while (scanf("%d", &N), N) { memset(head, 0, sizeof (head)); pos = 0; // 由于是静态的边，所以这里需要回溯pos指针 for (int i = 1; i <= N; ++i) { scanf("%d %d", &e[i].x, &e[i].y); } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { insert(i, j); } } printf("Scenario #%d\n", ++ca); printf("Frog Distance = %.3lf\n\n", SPFA()); } return 0;}