阅读原文
背景：\(Codeforces\) \(Round\) \(\#302\) \((Div. 1)\) \(B\) 题， \(Codeforces543B\) 给定一张边权全为 \(1\) 的图。在保证点 \(s_1\) 到点 \(t_1\) 的距离不超过 \(l_1\) 且点 \(s_2\) 到点 \(t_2\) 的距离不超过 \(l_2\) 的条件下，求最多能删去的边数。如果没有合法方案，输出 \(-1\) 。 这题最关键的就是转化模型。一开始我死都没想到正解就是因为忽略了边权全为 \(1\) 。 设点 \(i\) 到点 \(j\) 的最短长度为 \(dis[i][j]\) 。这时原条件就可以转化成求点 \(s_1\) 到点 \(t_1\) 的最短路上和点 \(s_2\) 到点 \(t_2\) 的最短路上经过的路径边数之和。 当然，这其中有 \(3\) 种情况： 第一种是点 \(s_1\) 到点 \(t_1\) 的最短路和点 \(s_2\) 到点 \(t_2\) 的最短路没有重叠部分。这个时候两个最短路值直接相加就行。 第二种是点 \(s_1\) 到点 \(t_1\) 的最短路和点 \(s_2\) 到点 \(t_2\) 的最短路在点 \(i\) 和点 \(j\) 之间重叠。这个时候可以 \(O(n^2)\) 枚举重叠点 \(i\) 和 \(j\) ，在保证路长限制的情况下更新答案就行，答案是 \(dis[s_1][i]+dis[s_2][i]+dis[i][j]+dis[j][t_1]+dis[j][t_2]\) 。 第三种也是点 \(s_1\) 到点 \(t_1\) 的最短路和点 \(s_2\) 到点 \(t_2\) 的最短路在点 \(i\) 和点 \(j\) 之间重叠，但是点 \(s_2\) 到点 \(t_2\) 的最短路从点 \(i\) 走向点 \(j\) ，而点 \(s_1\) 到点 \(t_1\) 的最短路从点 \(j\) 走向点 \(i\) 。 这个时候做法同上，答案是 \(dis[s_1][j]+dis[s_2][i]+dis[i][j]+dis[i][t_1]+dis[j][t_2]\) 。 至于求任意两点的最短路嘛，做 \(n\) 遍 \(bfs\) 就行。 整个过程就是这样，如果还有什么不明白的，评论区见！感谢您的耐心阅读！ 代码如下：
#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n,m,x,y,s1,s2,t1,t2,l1,l2,ans; int num,head[6005],dis[3005][3005],vis[3005]; struct edge { int ver,nxt; }e[6005]; queue<int> q; inline void adde(int u,int v) { e[++num].ver=v; e[num].nxt=head[u]; head[u]=num; } inline void bfs(int s) { memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(register int i=head[x];i;i=e[i].nxt) { int y=e[i].ver; if(vis[y]) continue; vis[y]=1; dis[s][y]=dis[s][x]+1; q.push(y); } } } int main() { n=read(); m=read(); for(register int i=1;i<=m;i++) { x=read(); y=read(); adde(x,y); adde(y,x); } for(register int i=1;i<=n;i++) bfs(i); s1=read(); t1=read(); l1=read(); s2=read(); t2=read(); l2=read(); if(dis[s1][t1]>l1||dis[s2][t2]>l2) { printf("-1\n"); return 0; } ans=dis[s1][t1]+dis[s2][t2]; for(register int i=1;i<=n;i++) { for(register int j=1;j<=n;j++) { if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2) ans=min(ans,dis[s1][i]+dis[i][j]+dis[j][t1]+dis[s2][i]+dis[j][t2]); if(dis[s1][j]+dis[i][j]+dis[i][t1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2) ans=min(ans,dis[s1][j]+dis[i][j]+dis[i][t1]+dis[s2][i]+dis[j][t2]); } } printf("%d\n",m-ans); return 0; }转载于:https://www.cnblogs.com/Peter0701/p/11519439.html
相关资源：JAVA上百实例源码以及开源项目