[CSP-J2019 江西] 道路拆除 题解

• 2021 年 5 月 9 日
• 筆記

发现大家都是将路径拆成三条链来做，这里提供一种暴力的乱搞方法。

思路

看到这一道题的第一想法就是跑最短路。可是仔细想想就发现，由于重合的路径只算一遍，所以导致两条最短路不一定是最优解。

接着，看到数据范围中的 \(m\leq 3000\) 告诉我们这个无向图是稀疏图。也就是说，从 \(1\) 到 \(s1,s2\) 的简单路径（重复走过点或边没有意义）总数不会很多。因此，我们就可以穷举 \((1,s1),(1,s2)\) 的所有简单路径，求最小经过的边即可。

只要加上以下的基础剪枝即可：

• 如果经过的边数已经超过目前最小值，返回。

• 如果路径长度已经超过 \(t1\) or \(t2\)，返回。

代码

有详细注释。

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=3010;
const int inf=10000000;
inline int read()
{
	register int x=0;
	register char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
int n,m;
int ans=inf;
int s1,s2,t1,t2;
vector<int>v[maxn],w[maxn];
bool k[maxn],Vis[maxn];
queue<int>q;
void DFS(int x,int len,int Len)
{
	if(x==s2)
	{
		ans=min(ans,len);//刷新最小值
		return ;
	}
	if(Len==t2||len>=ans) return ;
    //超过路程限制或者已经比当前答案劣
	for(register int i=0;i<v[x].size();i++)
		if(!Vis[w[x][i]])
		{
			Vis[w[x][i]]=1;
			DFS(v[x][i],len+!k[w[x][i]],Len+1);
			Vis[w[x][i]]=0;
		}
}
void dfs(int x,int len)
{
	if(x==s1)
	{
		DFS(1,len,0);
     //对于当前路径穷举 (1,s2) 的所有简单路径
		return ;
	}
	if(len==t1) return ;//如果超过路程限制
	for(register int i=0;i<v[x].size();i++)
		if(!k[w[x][i]])
				k[w[x][i]]=1,dfs(v[x][i],len+1),k[w[x][i]]=0;
}
int main()
{
	n=read(),m=read();
	register int x,y;
	for(register int i=1;i<=m;i++)
		x=read(),y=read(),v[x].pb(y),v[y].pb(x),w[x].pb(i),w[y].pb(i);
   //w数组存储的是边的编号
	s1=read(),t1=read(),s2=read(),t2=read();
	dfs(1,0);//穷举 (1,s1) 的所有简单路径
	if(ans==inf)
   //如果没有路径可以满足t1和t2的限制
		cout<<-1<<endl;
	else
		cout<<m-ans<<endl;
	return 0;
}