【题解】NOIP2018 旅行

\(\text{Solution:}\)

首先题目描述有一点不准确：回头是必须要走完一条路无路可走的时候才能返回。

对于树的情况：显然贪心做就完事了。

对于基环树的情况：对于一个\(n\)条边的环，如果我们已经走了\(n-1\)条边，那么此时我们已经可以到达环上任意一点了。所以我们可以枚举并删边。

题目中要求一个点除非回溯否则不能再次访问，这意味着一定有一条边无法访问，枚举那一条边即可。

时间复杂度\(O(n^2).\)

#include<bits/stdc++.h>

using namespace std;

const int inf=(1<<30);

int n,m,E[5001][2];

vector<int>G[5001];

namespace P1{

	vector<int>ans;

	void dfs(int x,int y){

		ans.push_back(x);

		for(int i=0;i<G[x].size();++i){

			int j=G[x][i];

			if(j==y)continue;

			dfs(j,x);

		}

	}

	void solve(){

		dfs(1,0);

		for(int i=0;i<ans.size();++i)printf("%d ",ans[i]);

		puts("");

	}

}

namespace P2{

	vector<int>ans,res;

	bitset<5001>vis;

	int Dv,Du;

	void dfs(int x,int fa){

		res.push_back(x);vis[x]=1;

		for(int i=0;i<G[x].size();++i){

			int j=G[x][i];

			if((x==Du&&j==Dv)||(x==Dv&&j==Du)||vis[j]||j==fa)continue;

			dfs(j,x);

		}

	}

	inline bool check(){

		for(int i=0;i<n;++i){

			if(ans[i]!=res[i]){

				if(ans[i]>res[i])return false;

				return true;

			}

		}

		return true;

	}

	void solve(){

		for(int i=0;i<n;++i)ans.push_back(inf),res.push_back(0);

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

			res.clear();vis.reset();

			Du=E[i][0],Dv=E[i][1];

			dfs(1,0);

			for(;(int)res.size()<n;)res.push_back(inf);

			if(!check())swap(res,ans);

		}

		for(int i=0;i<n;++i)printf("%d ",ans[i]);

		puts("");

	}

}

int main(){

	scanf("%d%d",&n,&m);

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

		int x,y;

		scanf("%d%d",&x,&y);

		G[x].push_back(y);

		G[y].push_back(x);

		E[i][0]=x,E[i][1]=y;

	}

	for(int i=1;i<=n;++i)sort(G[i].begin(),G[i].end());

	if(m==n-1){P1::solve();return 0;}

	P2::solve();

	return 0;

}

巴特西

【题解】NOIP2018 旅行

最新文章

热门文章