Codeforces Round #302 (Div. 2) D - Destroying Roads 图论，最短路

2019-11-06 07:15:15

字体：大中小

来源：转载

供稿：网友

题目链接:

http://codeforces.com/contest/544/PRoblem/D

题意:

有n个城镇，m条边权为1的双向边让你破坏最多的道路，使得从s1到t1，从s2到t2的距离分别不超过l1和l2

题解:

跑一发最短路，然后最后留下的图肯定是出了s1-t1,s2-t2这两条路之外，其他路都被删除了那么我们枚举重叠的道路就好了【可能反向】

代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//////////////////////////////////////////////////////////////////////////const int maxn = 3e3+10;int inq[maxn],d[maxn][maxn];vector<int> E[maxn];int main(){ int n=read(),m=read(); for(int i=0; i<m; i++){ int u=read(),v=read(); E[u].push_back(v); E[v].push_back(u); } int s1,t1,l1,s2,t2,l2; scanf("%d%d%d%d%d%d",&s1,&t1,&l1,&s2,&t2,&l2); for(int i=1; i<=n; i++){ MS(inq); for(int j=0; j<=n; j++) d[i][j] = INF; queue<int> q; q.push(i),inq[i]=1,d[i][i]=0; while(!q.empty()){ int now = q.front(); q.pop(),inq[now] = 0; for(int k=0; k<(int)E[now].size(); k++){ int v = E[now][k]; if(d[i][v] > d[i][now]+1){ d[i][v] = d[i][now]+1; if(inq[v]) continue; inq[v] = 1; q.push(v); } } } } if(d[s1][t1]>l1 || d[s2][t2]>l2){ cout << -1 << endl; return 0; } int ans = d[s1][t1]+d[s2][t2]; 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) ans = min(ans,d[s1][i]+d[i][j]+d[j][t1]+d[s2][i]+d[j][t2]); if(d[s1][i]+d[i][j]+d[j][t1]<=l1 && d[t2][i]+d[i][j]+d[j][s2]<=l2) // 反向的时候 ans = min(ans,d[s1][i]+d[i][j]+d[j][t1]+d[t2][i]+d[j][s2]); } cout << m-ans << endl; return 0;}/*10 111 32 33 44 54 63 73 84 94 107 98 101 5 36 2 3*/

上一篇：基于hadoop2.7.3搭建多机环境（YARN+HA）

下一篇：垃圾收集器与内存分配策略

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注