洛谷 P2149 [SDOI2009]Elaxia的路线 解题报告

P2149 [SDOI2009]Elaxia的路线

题目描述

最近,Elaxia和w**的关系特别好,他们很想整天在一起,但是大学的学习太紧张了,他们 必须合理地安排两个人在一起的时间。

Elaxia和w**每天都要奔波于宿舍和实验室之间,他们 希望在节约时间的前提下,一起走的时间尽可能的长。

现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图:地图上有\(N\)个路 口,\(M\)条路,经过每条路都需要一定的时间。 具体地说,就是要求无向图中,两对点间最短路的最长公共路径。

输入输出格式

输入格式:

第一行:两个整数\(N\)和\(M\)(含义如题目描述)。

第二行:四个整数\(x1\)、\(y1\)、\(x2\)、\(y2\) \((1 ≤ x1 ≤ N,1 ≤ y1 ≤ N,1 ≤ x2 ≤ N,1 ≤ y2 ≤ N)\),分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号(两对点分别 \(x1\),\(y1\)和\(x2\),\(y2\))。

接下来\(M\)行:每行三个整数,\(u\)、\(v\)、\(l\) \((1 ≤ u ≤ N,1 ≤ v ≤ N,1 ≤ l ≤ 10000)\),表\(u\)和\(v\)之间有一条路,经过这条路所需要的时间为\(l\)。

输出格式:

一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)

说明

对于30%的数据,N ≤ 100;

对于60%的数据,N ≤ 1000;

对于100%的数据,N ≤ 1500,输入数据保证没有重边和自环。


这道题对于现在的我来说,还是很有难度滴。

题目已经像是什么模板的问题:

求无向图中,两对点间最短路的最长公共路径

为什么会产生有选择的最长公共路径?因为最短路不只有一条啊。那么问题来了,如果求出最短路的所有边呢?

这里提供一种比较大众的做法。

对于图\(G\)中两点\(s,t\),用最短路算法求解以\(s\)和\(t\)为起始点的\(diss\)和\(dist\)数组。

那么对于边\(E(u,v,w)\),若它在最短路上,那么一定满足

\(diss[u]+w+dist[v]==diss[t]\)

这样的话,我们就解决了找在最短路上的边的问题。

我们也可以处理出两个人共同经过的一些边。不过需要注意的是,这个题有点诡异,两个人面对面走过一条路居然也算是一起走了!!?

这里有个贪心,他们的最长公共路径一定是一条链(试试反证)

于是我们可以把共同经过的边剥离出来一波操作

不过这里我们讨论拓扑排序的做法

回顾一下拓扑排序,它可以将图的操作按照一定的顺序操作而避免冲突。

我们取Elaxia的最短路集合和他们俩最短路的交集构成一个新的有向图(按照Elaxia的走路方向即可),特殊标记最短路交集的那些边

令\(dp[i]\)代表已经处理节点\(i\)所有前驱节点后所得到的最长公共路径。

转移:\(dp[i]=max(dp[i],dp[pre]+is*w);\)

\(pre\)为某前驱节点,\(is\)表示是否被特殊标记,\(w\)边长


code(常数炒鸡大啊):

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=1503;
int n,m,s[5];
struct Edge {int from,to,next,w;}edge[N*N];
int head[N],cnt=0;
int dis[5][N];
void add(int u,int v,int w)
{
edge[++cnt].to=v;edge[cnt].from=u;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt;
}
struct Edge0 {int to,next,w,is;}edge0[N*N];
int head0[N],cnt0=0;
void add0(int u,int v,int w,int is)
{
edge0[++cnt0].to=v;edge0[cnt0].w=w;edge0[cnt0].next=head0[u];edge0[cnt0].is=is;head0[u]=cnt0;
}
queue <int > q;
int used[N],in[N];
void spfa()
{
memset(dis,0x3f,sizeof(dis));
for(int k=1;k<=4;k++)
{
used[s[k]]=1;
dis[k][s[k]]=0;
q.push(s[k]);
while(!q.empty())
{
int u=q.front();
q.pop();
used[u]=0;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to,w=edge[i].w;
if(dis[k][v]>dis[k][u]+w)
{
dis[k][v]=dis[k][u]+w;
if(!used[v]) {used[v]=1;q.push(v);}
}
}
}
}
} void build()
{
for(int i=1;i<=cnt;i++)
{
int u=edge[i].from,v=edge[i].to,w=edge[i].w;
if(dis[1][u]+w+dis[2][v]==dis[1][s[2]])
{
if(dis[3][u]+w+dis[4][v]==dis[3][s[4]]||dis[3][v]+w+dis[4][u]==dis[4][s[3]])
add0(u,v,w,1);
else
add0(u,v,w,0);
in[v]++;
}
}
}
int dp[N];
void topo()
{
q.push(s[1]);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head0[u];i;i=edge0[i].next)
{
int v=edge0[i].to,w=edge0[i].w,is=edge0[i].is;
in[v]--;
dp[v]=max(dp[v],dp[u]+is*w);
if(!in[v])
q.push(v);
}
}
} int main()
{
int u,v,w;
scanf("%d%d",&n,&m);
scanf("%d%d%d%d",s+1,s+2,s+3,s+4);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w),add(v,u,w);
}
spfa();
build();
topo();
printf("%d\n",dp[s[2]]);
return 0;
}

2018.5.24

上一篇:学习OpenResty的正确姿势


下一篇:读取本地外网IP地址