[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;
}