对于30%的数据,N ≤ 100;
对于60%的数据,N ≤ 1000;
对于100%的数据,N ≤ 1500,输入数据保证没有重边和自环。
题解Here!
题目已经很明确:求无向图中,两对点间最短路的最长公共路径。
首先,分别从 s1?,t1,s2,t2? 为源点分别跑一次 spfa
记 path[1][u],path[2][u],path[3][u],path[4][u] 分别为从 s1?,t1,s2,t2?? 为起点到点 u 的最短路径。
于是构建出一个新的有向图,只包含 s1?−>t1? 的所有最短路上的边。
判断一条边 u−>v 是否在 s1?−>t1? 的最短路上,就是判断 path[1][u]+val(u,v)+path[2][v]==path[1][t1?] (val(u,v) 为边 u−>v 的长度),如果是,那么在最短路上,否则不在最短路上。
在新图中,标记出所有在 s2?−>t2? 的最短路上的边,方法也是一样。
但是要注意一点,对于新图中一条符合条件的边 u−>v , s2?−>t2? 的最短路径上这条边的走向可能是 u−>v ,也可能是 v−>u 。
所以,对于一条边必须判断两次:
第一次为 s2?−>u−>v−>t2? ,第二次为 s2?−>v−>u−>t2? ,若至少一次判断为真,则这条边在 s2?−>t2? 的最短路上。
最后,按照新图的拓扑序,在各个点之间进行递推即可:
sum[v]=max( sum[v] ,sum[u] + val(u,v) × flag )( flag 表示 u−>v 是否同时在 s1?−>t1? 最短路与 s2?−>t2? 最短路上)
附代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #define MAXN 1510 #define MAX 999999999 using namespace std; int n,m,c=2,d=2,s1,s2,t1,t2; int head[MAXN],h[MAXN],num[MAXN],sum[MAXN],path[5][MAXN]; bool vis[MAXN]; struct node{ int next,to,w; }a[MAXN*MAXN<<1]; struct node2{ int next,to,w; bool f; }b[MAXN*MAXN<<1]; inline int read(){ int date=0,w=1;char c=0; while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();} return date*w; } inline int relax(int u,int v,int w,int k){ if(path[k][v]>path[k][u]+w){ path[k][v]=path[k][u]+w; return 1; } return 0; } inline void add_one(int u,int v,int w){ a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++; a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++; } inline void add_two(int u,int v,int w,bool f){ b[d].to=v;b[d].w=w;b[d].f=f;b[d].next=h[u];h[u]=d++; } void spfa(int s,int k){ int u,v; queue<int> q; for(int i=1;i<=n;i++){path[k][i]=MAX;vis[i]=false;} path[k][s]=0; vis[s]=true; q.push(s); while(!q.empty()){ u=q.front(); q.pop(); vis[u]=false; for(int i=head[u];i;i=a[i].next){ v=a[i].to; if(relax(u,v,a[i].w,k)&&!vis[v]){ vis[v]=true; q.push(v); } } } } void work(){ int u,v; queue<int> q; q.push(s1); while(!q.empty()){ u=q.front(); q.pop(); for(int i=h[u];i;i=b[i].next){ v=b[i].to; sum[v]=max(sum[v],sum[u]+b[i].w*b[i].f); if(--num[v]==0)q.push(v); } } printf("%d\n",sum[t1]); } void init(){ int u,v,w; n=read();m=read(); s1=read();t1=read();s2=read();t2=read(); for(int i=1;i<=m;i++){ u=read();v=read();w=read(); add_one(u,v,w); } spfa(s1,1);spfa(t1,2); spfa(s2,3);spfa(t2,4); for(int i=2;i<c;i++) if(path[1][a[i^1].to]+a[i].w+path[2][a[i].to]==path[1][t1]){ if(path[3][a[i^1].to]+a[i].w+path[4][a[i].to]==path[3][t2] ||path[4][a[i^1].to]+a[i].w+path[3][a[i].to]==path[3][t2])add_two(a[i^1].to,a[i].to,a[i].w,true); else add_two(a[i^1].to,a[i].to,a[i].w,false); num[a[i].to]++; } } int main(){ init(); work(); return 0; }
原文:https://www.cnblogs.com/Yangrui-Blog/p/9281274.html