道路拆除的题解

发布时间:2024年01月10日

目录

原题描述:

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

题目大意:

主要思路:

至于dis怎么求?

代码code:


原题描述:

题目描述

A 国有?n座城市,从?1 \sim n?编号。1?号城市是 A 国的首都。城市间由?m?条双向道路连通,通过每一条道路所花费的时间均为?11?单位时间。

现在 A 国打算拆除一些不实用的道路以减小维护的开支,但 A 国也需要保证主要线路不受影响。因此 A 国希望道路拆除完毕后,利用剩余未被拆除的道路,从 A 国首都出发,能到达?s_1号与?s_2?号城市,且所要花费的最短时间分别不超过?t_1??与?t_2?(注意这是两个独立的条件,互相之间没有关联,即不需要先到?s_1??再到s_2)。

A 国想请你帮他们算算,在满足上述条件的情况下,他们最多能拆除多少条道路。 若上述条件永远无法满足,则输出?-1

输入格式

第一行两个正整数?n,m,表示城市数与道路数。

接下来?m?行,每行两个正整数?x,y,表示一条连接?x?号点与?y?号点的道路。数据保证没有重边和自环。

最后一行四个整数,分别为??s_1,??t_1,?s_2?,t_2,。

输出格式

仅一行一个整数,表示答案。

样例 #1

样例输入 #1

5 6
1 2
2 3
1 3
3 4
4 5
3 5
5 3 4 3

样例输出 #1

3

样例 #2

样例输入 #2

3 2
1 2
2 3
2 2 3 1

样例输出 #2

-1

提示

【数据范围】

对于?30\%?的数据,n,m\le 15

另有?20\%?的数据,n \le 100,m = n-1

另有?30\%?的数据,s_1 = s_2

对于?100\%的数据,2 \le n,m \le 3000,1\le x,y \le n,2 \le s_1,s_2 \le n,0 \le t_1,t_2 \le n

【样例?1?解释】

拆除?(1,2),(2,3),(3,4)三条边。

注意:不需要令首都与除了?s_1,s_2外的点在拆除之后依然连通。

【样例?2?解释】

即使一条边都不拆除,首都到?3?号点的最短时间也都达到了?2?单位时间。

题目大意:

给你一个无向图,问你最少可以去掉多少条边,可以使1到s_1的最短距离<=t_1,使1到s_2的最短距离<=t_2

主要思路:

首先分析一下,如果想最短,那么一定是形如这样的形式。

这样一定是最短的,那么我们就可以用一个dis数组来表示。

dis[3][3010]

dis[0][i]表示,从1走到i的最短路径。

dis[1][i]表示,从s1走到i的最短路径。

dis[2][i]表示,从s2走到i的最短路径。

那么当(dis[0][i]+dis[1][i]+dis[2][i])最小时且dis[0][i]+dis[1][i]<=t1,dis[0][i]+dis[2][i]<=t2。

m-(dis[0][i]+dis[1][i]+dis[2][i])就是答案了。

至于dis怎么求?

由于题目中说过,每条边的时间是1,就是边权为1,既然边权为1,那么可以用bfs求。

代码code:

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> v(3010);
int dis[10][3010];
int ans=0x3f3f3f3f;
void bfs(int x,int* tmpdis)//由于传数组,用指针
{
	tmpdis[x] = 0;
	queue<pair<int,int>> q;
	q.push({x,0});
	while(!q.empty())
	{
		int u=q.front().first,step=q.front().second;
		q.pop();
		for(auto it:v[u])
		{
			if(tmpdis[it] == 0x3f3f3f3f)
			{
				tmpdis[it] = step+1;
				q.push({it,step+1});
			}
		}
	}
	//是不是很像最短路?
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v1;
		cin>>u>>v1;
		v[u].push_back(v1);
		v[v1].push_back(u);
	}
	int s1,s2,t1,t2;
	cin>>s1>>t1>>s2>>t2;
	memset(dis,0x3f,sizeof(dis));//dis初始化
	bfs(1,dis[0]);
	bfs(s1,dis[1]);
	bfs(s2,dis[2]);
	//求三个dis。
	for(int i=1;i<=n;i++)
	{
		if(dis[0][i]+dis[1][i]<=t1&&dis[0][i]+dis[2][i]<=t2)
		{
			ans = min(ans,dis[0][i]+dis[1][i]+dis[2][i]);//计算
		}
	}
	cout<<(ans == 0x3f3f3f3f?-1:m-ans);//三目运算符,当无答案时,用-1
	return 0;
}


?

文章来源:https://blog.csdn.net/a613322/article/details/135500404
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。