最短路的两种变形
原题链接：传送门
题目大意
给定一个图，求出图中给定起点到终点的所有路径中，最长的那条边最小为多少？但是有几点特殊的情况需要处理：
- 题目给定的是二维坐标系的坐标形式，你需要自己求出来这些点之间的权值进行加边
- 对于权值的精度需处理要小心
分析
对于图论题目重要的过程在于分析和建模，如何能够解析出题意正确建图是很关键的一个环节。
对于此题，首先肯定排除求出所有的路径，再依次遍历所有路径的做法，时间复杂度不符合题目预设。
那么我们尝试只用一次遍历来解决这个问题。
通过分析我们发现题目中固定了起点和终点，这种模式和最短路算法比较相近，我们考虑如何能够使用最短路的方法来求解此问题。
我们将最短路径中表示记录起点到某个点的距离的数组给改变一下，dis[x] 表示 从起点开始到x点的路径中最长的那条边中最短的边的权值 。
于是我们更新dis[y] 有以下方式:
(dis[y] = min(dis[y] , max(dis[x] , w(x , y))))
void dijkstra(int s)
{
for(int i = 1;i <= n ;i ++)dis[i] = 999999.0;
memset(vis , 0 , sizeof vis);
dis[s] = 0;
for(int j = 0;j < n ;j ++)
{
int x = -1;
for(int i = 1;i <= n ;i ++)
{
if(!vis[i] && (x == -1 || dis[i] < dis[x]))x = i;
}
vis[x] = 1;
for(int i = head[x] ; i != -1 ;i = e[i].next)
{
int y = e[i].to;
dis[y] = min(dis[y] , max(e[i].w , dis[x]));
}
}
}
注意事项
- 对于输出需要用%.3f
- 提交需要用C++ 看巨巨们的博客说是精度问题
AC 代码
C++ code
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int N = 505;;
const int M = 50005;
struct edge{
int to , next;
double w;
}e[M];
int head[N] , tot , vis[N] , test;
double dis[N]; // dis[i]标识从1出发到达该点的所有边中的最大边
void add(int a,int b,double c)
{
e[++tot].to = b;
e[tot].w = c;
e[tot].next = head[a];
head[a] = tot;
}
int n;
struct node{
int x , y;
node(int a,int b):x(a) , y(b){}
};
double getdis(int a,int b,int c,int d)
{
return sqrt(double((a - c) * (a - c)) + double((b - d) * (b - d)));
}
void dijkstra(int s)
{
for(int i = 1;i <= n ;i ++)dis[i] = 999999.0;
memset(vis , 0 , sizeof vis);
dis[s] = 0;
for(int j = 0;j < n ;j ++)
{
int x = -1;
for(int i = 1;i <= n ;i ++)
{
if(!vis[i] && (x == -1 || dis[i] < dis[x]))x = i;
}
vis[x] = 1;
for(int i = head[x] ; i != -1 ;i = e[i].next)
{
int y = e[i].to;
dis[y] = min(dis[y] , max(e[i].w , dis[x]));
}
}
}
void slove()
{
tot = 0;
memset(head , -1 , sizeof head);
vector<node> v;
for(int i = 0;i < n ;i ++)
{
int x, y ;cin >> x >> y;
v.push_back(node(x , y));
}
for(int i = 0;i < v.size() ;i ++)
{
for(int j = i + 1;j < v.size() ;j ++)
{
double dis = getdis(v[i].x , v[i].y , v[j].x ,v[j].y);
//printf("%d -> %d %f
",i + 1 , j + 1 , dis );
add(i + 1,j + 1, dis);
add(j + 1,i + 1, dis);
}
}
dijkstra(1);
printf("Scenario #%d
", test);
printf("Frog Distance = %.3f
", dis[2]);
}
int main()
{
while(cin >> n && n)
{
test++;
slove();
}
return 0;
}
启发
此类问题是最短路问题的一类变形问题，即虽然固定了起点和终点，但是却并不是让我们直接去求解两点之间的最短路径长度，而是所有从起点通向终点的路径中最长的那一条的最小值，当然我们也可以对此问题在进行变形。
例如求解所有路径中最小值边的最大值(POJ-1797)呀等等变形。
那么我们就要从最短路的意义出发，思考为什么最短路可以解决此类问题