51nod破坏道路 1444

题意：

1444 破坏道路
1.5 秒 131,072.0 KB 80 分 5级题
在某一个国家，那儿有n个城市，他们通过m条双向道路相连。城市从1到n编号。如果城市a和b通过一条道路直接相连，那么他们之间的距离就是一个小时。这个国家的道路网络可以允许你从任意一个城市到达另外的城市。

现在你要破坏尽可能多的道路，但是要保证从城市s1到t1不超过l1小时，并且从城市s2到t2不超过l2小时。

输出最多可以破坏的道路数目，如果没有解，请输出-1

输入
单组测试数据。
第一行有两个整数n,m(1 ≤ n ≤ 3000, n-1 ≤ m ≤ min(3000,n*(n-1)/2) )。
接下来m行，每行有两个整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)，表示ai和bi之间有一条道路。
输入保证是一个连通图。
最后两行每行有三个整数s1, t1, l1和 s2, t2, l2, (1 ≤ si, ti ≤ n, 0 ≤ li ≤ n)。
输出
输出一个整数，表示最多可以破坏的道路数目，如果没有解，输出-1。
输入样例
5 4
1 2
2 3
3 4
4 5
1 3 2
3 5 2
输出样例
0

思路：

（BFS + 枚举）
我应该是菜到极点了，不会更菜了。。。。。
每天上班时头脑是清醒滴。。。。几道题过后就是晕的。。。。

（1）首先还是最短路径，因为每条路径的长度是1，那么我们肯定就可以bfs求任意两点之间的距离。。。

当然上面这些我看到这道题就想到了，嘤嘤嘤！！！
下面的是没有想到的，呜呜呜！！！

（2）因为我们要破坏尽可能多的道路，那么我们尽量让s1 -> t1 和 s2 -> t2的路径重叠的尽可能多，然后就是n ^ 2复杂度枚举重叠的路径的端点。

（3）注意⚠️判断无解的情况

附加分析：

那么我当时为什么觉得这道题我写不出来呢：
1.我认为不超过l1和不超过l2，只是一个范围，情况多种多样，处理就无从下手
2.我考虑的是每次去边的时候，每次只去掉一条边，那么最优解里有没有包含这条边，是不清楚的，也没办法处理

反思：
我应该有整体思维，把边一起去掉，不要只关心局部

代码实现：

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
const int inf = 0x3f3f3f3f;int n,m;
vector<int> G[maxn];
int s1,t1,l1,s2,t2,l2;
int dis[3005][3005];
queue<int> q;
int vis[3005];void bfs(int s){while(!q.empty()) q.pop();memset(vis,0,sizeof(vis));dis[s][s] = 0;q.push(s);vis[s] = 1;while(!q.empty()){int e = q.front(); q.pop();int len = G[e].size();for(int i = 0;i < len;i++){int v = G[e][i];if(!vis[v]){dis[s][v] = dis[s][e] + 1;vis[v] = 1;q.push(v);}}}
}int main(){scanf("%d%d",&n,&m);int u,v;for(int i = 1;i <= m;i++){scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}scanf("%d%d%d%d%d%d",&s1,&t1,&l1,&s2,&t2,&l2);for(int i = 1;i <= n;i++) bfs(i);if(dis[s1][t1] > l1||dis[s2][t2] > l2){printf("-1\n");return 0;}int ans = dis[s1][t1] + dis[s2][t2];for(int i = 1;i <= n;i++){for(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(dis[s1][i]+dis[i][j]+dis[j][t1]+dis[s2][i]+dis[j][t2],ans);}if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[t2][i]+dis[i][j]+dis[j][s2]<=l2){ans = min(dis[s1][i]+dis[i][j]+dis[j][t1]+dis[t2][i]+dis[j][s2],ans);}if(dis[t1][i]+dis[i][j]+dis[j][s1]<=l1&&dis[t2][i]+dis[i][j]+dis[j][s2]<=l2){ans = min(dis[t1][i]+dis[i][j]+dis[j][s1]+dis[t2][i]+dis[j][s2],ans);}if(dis[t1][i]+dis[i][j]+dis[j][s1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2){ans = min(dis[t1][i]+dis[i][j]+dis[j][s1]+dis[s2][i]+dis[j][t2],ans);}}}printf("%d\n",m - ans);return 0;
}

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