本文主要是介绍Codeforces Round #302 (Div. 1) B. Destroying Roads (思维+bfs+最短路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/543/problem/B
题目大意：给出一张边权为1的无向图，并给出s1 t1 l1,s2 t2 l2，要求删最多的边使s1到t1的路小于等于l1,s2到t2的路小于等于l2
题目思路：边权相等的图可以用bfs O(n^2)得到任意两点的最短距离！！！
刚开始没想到上述结论，于是就自闭了...如果知道的话，直接先暴力出所有距离，然后可以发现一个事情，就是删掉最多的边等价于留下最少的边，想让边尽可能少，要么两边都走各自最短路，要么就是通过公共边省了一段路，公共边一定只有一条，因为如果分叉的话一定会有一个更好或者一样好，也就没必要分叉了，所以先判一下两个都走最短路行不行，然后枚举中间这条公共边，注意一个坑点，就是两个可能经过共同边的方向是相反的！！
以下是代码：
#include<bits/stdc++.h>using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 3e3+5;
int n,m,x,y;
vector<int>v[MAXN];
int s1,t1,l1,s2,t2,l2;
int dis[MAXN][MAXN];
queue<int>q;
bool vis[MAXN];
int main()
{while(~scanf("%d%d",&n,&m)){while(!q.empty())q.pop();rep(i,1,n)v[i].clear();rep(i,1,m){scanf("%d%d",&x,&y);v[x].push_back(y);v[y].push_back(x);}scanf("%d%d%d%d%d%d",&s1,&t1,&l1,&s2,&t2,&l2);memset(dis,0x3f,sizeof(dis));rep(i,1,n){dis[i][i]=0;memset(vis,0,sizeof(vis));vis[i]=1;q.push(i);while(!q.empty()){int u=q.front();q.pop();int len=v[u].size();rep(j,0,len-1){int y=v[u][j];if(vis[y])continue;vis[y]=1;q.push(y);dis[i][y]=dis[i][u]+1;}}}int ans=1e9;if(dis[s1][t1]<=l1&&dis[s2][t2]<=l2)ans=min(ans,dis[s1][t1]+dis[s2][t2]);rep(i,1,n){rep(j,1,n){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[s2][i]+dis[i][j]+dis[j][t1]+dis[j][t2]);}if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][j]+dis[j][i]+dis[i][t2]<=l2){ans=min(ans,dis[s1][i]+dis[s2][j]+dis[i][j]+dis[j][t1]+dis[i][t2]);}}}if(ans==1e9)puts("-1");else printf("%d\n",m-ans);}return 0;
}
这篇关于Codeforces Round #302 (Div. 1) B. Destroying Roads (思维+bfs+最短路)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
