【算法系列学习】Dijkstra算法变形 [kuangbin带你飞]专题四 最短路练习

时间:2024-09-17 10:04:32

https://vjudge.net/contest/66569#problem/B

类试题:noip2013 货物运输

POJ 1797 Heavy Transportation

方法一: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