NOIP2018旅行

这道题考场上的时候暴力写RE了，我果然很菜。

看了一篇大佬的的题解才明白 dalao的题解

但是解释很少哇，为了造福人类，在下发一篇详细一点的题解。

预处理：用vector把与每个点相连的点存起来，排一遍序。

m=n-1的情况

这种比较好处理，搜到一个节点后找一个与该节点相连的最小的编号的儿子继续往下搜，显然这样答案更优。不过要小心RE。

具体代码就是：



void work(int u,int fa)

{

	if(vis[u]) return ;

	vis[u]=1;

	ans[++dep]=u;

	for(int i=0;i<vec[u].size();++i)

	{

		int v=vec[u][i];

		if(v==fa)

		  continue;

		work(v,u);

	}

}

比较简单一点的深搜的板子。

m=n的情况

基环树的情况不太好处理。但是基环树只有一个环，如果删去一条环上的边，那么就会变成一棵树。所以我们就暴力地枚举删哪条边，将所有答案求一个最优值。代码在洛谷上跑了900多毫秒，感觉有点虚……

不过有一个比较高效的优化:如果边不在环上，就不用搜了，因为在树上的边一定是要经过的。（可惜我不会...）

在主函数里特判一下：



	if(n==m)

	{

		for(int i=0;i<tot;i+=2)//因为加的是双向边，所以i+=2

		//如果你习惯tot从一开始，循环写成这样：for(int i=1;i<=tot;i+=2),恭喜你得到TLE的好成绩

		{

			dep=0; x=e[i].u; y=e[i].v;//x,y记录一下当前搜到的边

			memset(vis,0,sizeof(vis));

			dfs(1,-1);

			if(dep<n) continue;//说明枚举到的边不在环上

			if(ans[1]==0)

			 change();//统计答案

			else if(check()) change();//check比较哪个答案更优

		}

		for(int i=1;i<=n;++i)

		 printf("%d ",ans[i]);

		return 0;

	}

当然vector是比较慢的，可是我也不会优化.......

完整代码奉上：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

int n,m,ans[5050],tot,head[5050];

int k[5050],dep,x,y;

bool vis[5050];

vector <int> vec[5050];

struct edge{

	int u,v,next;

}e[10005];

void add(int x,int y)

{

	e[tot].u=x;

	e[tot].v=y;

	e[tot].next=head[x];

	head[x]=tot++;

}

inline int read()

{

	int ans=0,w=1;

	char c=getchar();

	while((c<'0'||c>'9')&&c!='-') c=getchar();

	if(c=='-') { w=-1; c=getchar();};

	while(c>='0'&&c<='9')

	{ ans=ans*10+c-'0'; c=getchar(); }

	return ans*w;

}

void dfs(int u,int fa)

{

	if(vis[u]) return;

	vis[u]=1;

	k[++dep]=u;

	for(int i=0;i<vec[u].size();++i)

	{

		int v=vec[u][i];

		if(v==fa) continue;

		if((v==y&&u==x)||(v==x&&u==y))

		 continue;

		dfs(v,u);

	}

}

bool check()

{

	for(int i=1;i<=n;++i)

	{

		if(k[i]==ans[i])

		 continue;

		if(k[i]>ans[i])

		 return false;

		else return true;

	}

}

void change()

{

	for(int i=1;i<=n;++i)

	 ans[i]=k[i];

}

void work(int u,int fa)

{

	if(vis[u]) return ;

	vis[u]=1;

	ans[++dep]=u;

	for(int i=0;i<vec[u].size();++i)

	{

		int v=vec[u][i];

		if(v==fa)

		  continue;

		work(v,u);

	}

}

int main()

{

	int u,v;

	memset(head,-1,sizeof(head));

	n=read(); m=read();

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

	{

		u=read(); v=read();

		vec[u].push_back(v);

		vec[v].push_back(u);

		add(u,v); add(v,u);

	}

	for(int i=1;i<=n;++i)

	 sort(vec[i].begin(),vec[i].end());

	if(n==m)

	{

		for(int i=0;i<tot;i+=2)

		{

			dep=0; x=e[i].u; y=e[i].v;

			memset(vis,0,sizeof(vis));

			dfs(1,-1);

			if(dep<n) continue;

			if(ans[1]==0)

			 change();

			else if(check()) change();

		}

		for(int i=1;i<=n;++i)

		 printf("%d ",ans[i]);

		return 0;

	}

	work(1,-1);

	for(int i=1;i<=n;++i)

	 printf("%d ",ans[i]);

	return 0;

}

巴特西

NOIP2018旅行

m=n-1的情况

m=n的情况

最新文章

热门文章