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

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

思路

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

接着，看到数据范围中的 \(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;

}

巴特西

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

思路

代码

最新文章

热门文章

巴特西

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

思路

代码

最新文章

热门文章

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