NOIp 2018 旅行 题解
程序员文章站
2024-03-20 10:54:46
...
题目大意: 现在有一棵树或一张只有一个环的图(连通),要求遍历一遍这个图,遍历的顺序即为一个长度为 的序列,要求字典序最小的序列。
题解
假如是一棵树的话,显然贪心即可,从 出发,每次往编号小的走就好了。
假如只是多一条边的话,枚举删掉那一条边,然后变成一棵树来做。
因为每次都要往编号小的走,所以我把当前点能到达的点都弄起来,然后 一下编号,因为大量使用 ,所以不开 过不了……
代码如下:
#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]);
}
上一篇: Django-会话跟踪cookie和session
下一篇: 竞赛题解 - NOIP2018 旅行