https://vjudge.net/contest/66569#problem/B
类试题：noip2013 货物运输
方法一：Dijkstra变形
http://blog.****.net/u013446688/article/details/42777173
关键在于对松弛的变形，这里不是求源点到每个点的所有路径中的路径长度最小值，而是求源点到每个点的所有路径中Frog distance(路径中的最大距离)的最小值
所以dis[k]=min(dis[k],dis[v]+map[v][k])变成了dis[k]=min(dis[k],max(dis[v],map[v][k]))
这里的dis[k]不再是源点到结点k所有路径中路径长度的最小值，而是源点到结点k所有路径中Frog distance（路径中的最大距离）的最小值。
为了理解dis[k]=min(dis[k],max(dis[v],map[v][k]))，我们可以做这样的假设：源点到v的路径有三条，这三条路径的frog distance分别是3,4,5;那么dis[v]就是3。
现在分两种情况分别进行讨论：
1.map[v][k]>dis[v],由于源点经过v到达k的路径也有三条，这三条的frog distance就分别变成了map[v][k],max(4,map[v][k]),max(5,map[v][k]);那么dis[k]就一定是最小值map[v][k].
2.map[v][k]<=dis[v],则这三条路径的frog distance 还是3,4,5.dis[k]就等于dis[v]
下面是AC的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
const double inf=0x3f3f3f3f;
using namespace std;
int n;
struct node
{
int x,y;
}nd[];
double map[][];
double dist(node a,node b)
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));
}
double dis[];
void Dijkstra()
{
bool vis[];
memset(vis,,sizeof(vis));
dis[]=0.0;
for(int i=;i<=n;i++)
{
dis[i]=inf;
}
int v;
for(int i=;i<=n;i++)
{
int m=inf;
for(int k=;k<=n;k++)
{
if(!vis[k]&&dis[k]<m)
{
m=dis[k];
v=k;
}
}
vis[v]=;
//对以v为顶点的边进行松弛
for(int k=;k<=n;k++)
{
if(!vis[k])
{
dis[k]=min(dis[k],max(dis[v],map[v][k]));
}
}
}
}
int main()
{
int kas=;
while(scanf("%d",&n)&&n)
{
for(int i=;i<=n;i++)
{
scanf("%d%d",&nd[i].x,&nd[i].y);
for(int k=;k<i;k++)
{
map[i][k]=map[k][i]=dist(nd[i],nd[k]);
}
}
Dijkstra();
if(kas!=)
{
printf("\n");
}
printf("Scenario #%d\n",kas++);
printf("Frog Distance = %.3f\n",dis[]);
}
return ;
}
Dijkstra
要注意四点:
1.sqrt()要强制转化为double
2.double不能用memset(dis,inf,sizeof(dis))
3.
for(int k=1;k<=n;k++)
{
if(!vis[k])
{
dis[k]=min(dis[k],max(dis[v],map[v][k]));
}
}
不写vis[k]也对，但是增加时间复杂度
4.注意输入输出,最后一个样例之后是没有空行的
方法二：二分+并查集
http://xwk.iteye.com/blog/2129453
二分出一个mid值表示最大边的长度，然后遍历所有边，只要当前边的长度不超过mid,就合并当前边所连接的两个点。最后判断1和2在不在同一个连通分量上，如果是则说明当前mid已经足够，为了找到mid的最小值，R=mid.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath> using namespace std;
const int maxn=2e2+;
const double eps=1e-;
int n;
struct node
{
int x,y;
}nd[maxn];
double map[maxn][maxn];
double dist(const node& a,const node& b)
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));
}
int fa[maxn];
int find(int i)
{
if(fa[i]==-)
{
return i;
}
return fa[i]=find(fa[i]);
}
bool bind(int i,int k)
{
i=find(i);
k=find(k);
if(i!=k)
{
fa[i]=k;
}
return true;
}
bool ok(double mid)
{
memset(fa,-,sizeof(fa));
//加进去的边的最大值为mid
for(int i=;i<=n;i++)
{
for(int k=i+;k<=n;k++)
{
if(map[i][k]<mid)
{
bind(i,k);
}
}
}
return find()==find();
} int main()
{
int kas=;
while(scanf("%d",&n)&&n)
{
for(int i=;i<=n;i++)
{
scanf("%d%d",&nd[i].x,&nd[i].y);
for(int k=;k<i;k++)
{
map[i][k]=map[k][i]=dist(nd[i],nd[k]);
}
}
double l=0.0;
double r=map[][];
while(r-l>eps)
{
double mid=(l+r)/;
if(ok(mid))
{
r=mid;
}
else
{
l=mid;
}
}
if(kas!=)
{
printf("\n");
}
printf("Scenario #%d\n",kas++);
printf("Frog Distance = %.3f\n",r);
}
return ;
}
二分+并查集
注意在ok函数里，每次都要初始化memset(fa,-1,sizeof(fa));
方法三：最小生成树
http://blog.****.net/shouwang_tomorrow/article/details/47616983
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath> using namespace std;
int n;
int cnt;
const int maxn=2e4+; struct edge
{
int x,y;
double w;
}e[maxn];
struct node
{
int x;
int y;
}nd[];
double dist(const node& a,const node& b)
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));
}
bool cmp(const edge& a,const edge& b)
{
return a.w<b.w;
}
int fa[maxn];
int find(int i)
{
if(fa[i]==-)
{
return i;
}
return fa[i]=find(fa[i]);
}
bool bind(int i,int k)
{
i=find(i);
k=find(k);
if(i!=k)
{
fa[i]=k;
return true;
}
return false;
}
double Kruskal()
{
for(int i=;i<cnt;i++)
{
if(bind(e[i].x,e[i].y))
{
if(find()==find())
{
return e[i].w;
}
}
}
}
int main()
{
int kas=;
while(scanf("%d",&n)&&n)
{
cnt=;
for(int i=;i<=n;i++)
{
scanf("%d%d",&nd[i].x,&nd[i].y);
for(int k=;k<i;k++)
{
e[cnt].x=i;
e[cnt].y=k;
e[cnt++].w=dist(nd[i],nd[k]);
}
}
sort(e,e+cnt,cmp);
memset(fa,-,sizeof(fa));
double ans=Kruskal();
if(kas!=)
{
printf("\n");
}
printf("Scenario #%d\nFrog Distance = %.3f\n",kas++,ans);
}
return ;
}
Kruskal