51Nod1444 破坏道路

题目看这里

也是非常套路的一道题

首先考虑，如果只有一组限制，那么答案就是m-l1

现在考虑加了一组限制的情况下有什么影响

显然，被两段路径重复覆盖的那一部分会多减掉一次

那么我们可以枚举这段路径，让后用dp来计算答案，注意因为是无权图可以bfs O(n^2)求出两点之间最短路

#pragma GCC opitmize("O3")
#pragma G++ opitmize("O3")
#include
#include
#include
#include
#define N 3010
using namespace std;
struct edge{ int v,nt; } G[6010];
int d[N][N],n,m,h[N],cnt=0; queue<int> q;
inline void gmin(int& x,int y){ x>y?x=y:0; }
int main(){scanf("%d%d",&n,&m);for(int x,y,i=1;i<=m;++i){scanf("%d%d",&x,&y);G[++cnt]=(edge){y,h[x]}; h[x]=cnt;G[++cnt]=(edge){x,h[y]}; h[y]=cnt;}for(int i=1;i<=n;++i){bool vis[N]={0};d[i][i]=0; q.push(i); vis[i]=1;for(int x;!q.empty();q.pop()){x=q.front();for(int v,j=h[x];j;j=G[j].nt)if(!vis[v=G[j].v]){ d[i][v]=d[i][x]+1; vis[v]=1; q.push(v); }}}int s1,t1,s2,t2,l1,l2,ans;scanf("%d%d%d%d%d%d",&s1,&t1,&l1,&s2,&t2,&l2); ans=d[s1][t1]+d[s2][t2];if(d[s1][t1]>l1 || d[s2][t2]>l2) return 0&puts("-1");for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){if(d[s1][i]+d[i][j]+d[j][t1]<=l1 && d[s2][i]+d[i][j]+d[j][t2]<=l2) gmin(ans,d[s1][i]+d[j][t1]+d[i][j]+d[s2][i]+d[j][t2]);if(d[t1][i]+d[i][j]+d[j][s1]<=l1 && d[s2][i]+d[i][j]+d[j][t2]<=l2) gmin(ans,d[t1][i]+d[j][s1]+d[i][j]+d[s2][i]+d[j][t2]);if(d[t1][i]+d[i][j]+d[j][s1]<=l1 && d[t2][i]+d[i][j]+d[j][s2]<=l2) gmin(ans,d[t1][i]+d[j][s1]+d[i][j]+d[t2][i]+d[j][s2]);if(d[s1][i]+d[i][j]+d[j][t1]<=l1 && d[t2][i]+d[i][j]+d[j][s2]<=l2) gmin(ans,d[s1][i]+d[j][t1]+d[i][j]+d[t2][i]+d[j][s2]);}printf("%d\n",m-ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！