P5022 [NOIP2018 提高组] 旅行
我只想出了部分分的解法。。。
https://fzy.blog.luogu.org/solution-p5022
#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
vector<int> a[5010];
int n,m;
int dis[5010],ans[5010],cnt;
int vis[5010];
int du,dv;
struct node{
int from,to;
}e[5010];
void dfs1(int u,int fa)
{
if(vis[u])
return ;
vis[u]=1;
dis[++cnt]=u;
for1(i,0,a[u].size()-1)
{
int v=a[u][i];
if(v==fa)
continue ;
if((u==du&&v==dv)||(u==dv&&v==du))
continue ;
dfs1(v,u);
}
}
void dfs2(int u,int fa)
{
if(vis[u]) return ;
vis[u]=1;
ans[++cnt]=u;
for1(i,0,a[u].size()-1)
{
int v=a[u][i];
if(v==fa) continue ;
dfs2(v,u);
}
}
int check()
{
for1(i,1,n)
{
if(dis[i]<ans[i])
return 1;
else if(dis[i]>ans[i])
return 0;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
int x,y;
for1(i,1,m)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
e[i].from=x;
e[i].to=y;
}
for1(i,1,n) sort(a[i].begin(),a[i].end());
if(m==n)
{
int kg=1;
for1(i,1,m)
{
du=e[i].from,dv=e[i].to;
memset(vis,0,sizeof(vis));
cnt=0;
dfs1(1,0);
if(cnt<n) continue ;
if(kg)
{
for1(i,1,n) ans[i]=dis[i];
kg=0;
}
if(check())
for1(i,1,n) ans[i]=dis[i];
}
for1(i,1,n) printf("%d ",ans[i]);
}
else
{
dfs2(1,0);
for1(i,1,n) printf("%d ",ans[i]);
}
return 0;
}
标签:5010,cnt,return,vis,19,dfs,NOIP2018,int,for1
From: https://www.cnblogs.com/yyx525jia/p/16806618.html