洛谷 P5683 【[CSPJX2019]道路拆除】

先用做的暴力，因为n最多才3000嘛，但是后来发现时间复杂度不止\(O\)（\({n}^2\)）,然后就放弃了。

讲讲我的暴力+错误思路吧：

把1到s1和s2的最短路算出来，用SPFA，然后用DFS求出所有的最短路的路径，然后两两枚举，看哪个重合的点数最多，然后输出其他点所连接的边的个数。如果你这样想，那就跟我一样错了。仔细读题，我们求的是删除的最大，也就是保留的最小，保留的是总和，而不是每一个都是最短路，所以思路错了（所以我好弱弱弱弱弱啊）。

正解：

1到s1和1到s2当中，两条路径肯定是有公共点的（1也算的），那么我们只需要枚举公共点即可。先用SPFA算出1，s1，s2到每一个点的最短路，然后枚举公共点，从1到n，设ans为能够联通s1，s2需要的最少的边，i为当前枚举到的点，dis1为1到每一个点的最短路，dis2为s1到每一个点的最短路，dis3为s2到每一个点的最短路，那么枚举过程就应该为\(ans\)\(=\)\(min\)（\(ans\),\(dis1_i+dis2_i+dis3_i\)）。

代码：SPFA没死

#include <bits/stdc++.h>

using namespace std;

int n , m , s1 , t1 , s2 , t2 , ans = 0x3fffff;

int vis[3010] , dis1[3010] , dis2[3010] , dis3[3010];

vector<int> e[3010];

int spfa(int x , int dis[]){

	queue<int> q;

	memset(vis , 0 , sizeof(vis));

	q.push(x);

	dis[x] = 0;

	vis[x] = 1;

	while(!q.empty()){

		int xx = q.front();

		q.pop();

		vis[xx] = 0;

		for(int i = 0; i < e[xx].size(); i++){

			int y = e[xx][i];

			if(dis[y] > dis[xx] + 1){

				dis[y] = dis[xx] + 1;

				if(!vis[y]){

					vis[y] = 1;

					q.push(y);

				}

			}

		}

	}

}

int main(){

	cin >> n >> m;

	for(int i = 1; i <= m; i++){

		int x , y;

		cin >> x >> y;

		e[x].push_back(y);

		e[y].push_back(x);

	}

	cin >> s1 >> t1 >> s2 >> t2;

	for(int i = 1; i <= n; i++) dis1[i] = dis2[i] = dis3[i] = 0x3ffffff;

	spfa(1 , dis1);	//跑三次SPFA

	spfa(s1 , dis2);

	spfa(s2 , dis3);

	if(dis1[s1] > t1 || dis1[s2] > t2){	//判断无法完成的情况

		cout << -1;

		return 0;

	}

	for(int i = 1; i <= n; i++)

		ans = min(ans , dis1[i] + dis2[i] + dis3[i]);

	cout << m - ans;	//因为求的是删除的，所以要用总的减用的

	return 0;

}

巴特西

洛谷 P5683 【[CSPJX2019]道路拆除】

讲讲我的暴力+错误思路吧：

正解：

最新文章

热门文章