欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOIp 2018 旅行 题解

程序员文章站 2024-03-20 10:54:46
...

题目传送门

题目大意: 现在有一棵树或一张只有一个环的图(连通),要求遍历一遍这个图,遍历的顺序即为一个长度为 nn 的序列,要求字典序最小的序列。

题解

假如是一棵树的话,显然贪心即可,从 11 出发,每次往编号小的走就好了。

假如只是多一条边的话,枚举删掉那一条边,然后变成一棵树来做。

因为每次都要往编号小的走,所以我把当前点能到达的点都弄起来,然后 sortsort 一下编号,因为大量使用 sortsort,所以不开 O2O2 过不了……

代码如下:

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
#define maxn 5010

struct edge{int x,y;};
edge edges[maxn];
int n,m;
bool v[maxn];
bool check(int *a,int *b)
{
	for(int i=1;i<=n;i++)
	if(a[i]<b[i])return true;
	else if(a[i]>b[i]) return false;
	return false;
}
int a[maxn],t;
int ans[maxn];
bool tf[maxn];
struct nod{int y,next;};
nod e[2*maxn];
int zhan[maxn],tt=0;
int len;
int first[maxn];
void dfs(int x)
{
	a[++t]=x;tf[x]=true;
	if(t==n)return;
	int st=tt+1;
	for(int i=first[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(tf[y])continue;
		zhan[++tt]=y;
	}
	if(st==tt+1)return;
	sort(zhan+st,zhan+tt+1);
	int ed=tt;
	for(int i=st;i<=ed;i++)
	if(!tf[zhan[i]])dfs(zhan[i]);
}
void buildroad(int x,int y)
{
	e[++len]=(nod){y,first[x]};
	first[x]=len;
}
void work()
{
	len=0;
	for(int i=1;i<=n;i++)
	tf[i]=false,first[i]=0;
	for(int i=1;i<=m;i++)
	if(!v[i])buildroad(edges[i].x,edges[i].y),buildroad(edges[i].y,edges[i].x);
	t=tt=0;
	dfs(1);
}

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	scanf("%d %d",&edges[i].x,&edges[i].y);
	if(m==n-1)
	{
		work();
		for(int i=1;i<=n;i++)
		printf("%d ",a[i]);
		return 0;
	}
	for(int i=1;i<=n;i++)//别忘了初始化ans数组
	ans[i]=999999999;
	for(int i=1;i<=m;i++)
	{
		v[i]=true;//删掉第i条边
		work();
		if(t==n&&check(a,ans))
		{
			for(int j=1;j<=n;j++)
			ans[j]=a[j];
		}
		v[i]=false;
	}
	for(int i=1;i<=n;i++)
	printf("%d ",ans[i]);
}