CF453C Little Pony and Summer Sun Celebration

前言

屑黑题。
【题目传送门】

题解

构造题。
不需要想的太过于复杂，如果一个劲只想着怎么走让某个点达到目标，这题就做不出来了。
构造题，先瞎搞，再看看能不能得到答案。
先按照 DFS 生成一个树，就构造出来了每个点经过的次数的一种方案。
考虑怎么让它合法，如果回溯的时候发现 (u) 还不合法，就在 (u,fa) 之间横跳一次，(u) 就合法了。往上就以此类推。
注意特判根节点的情况，同时由于图不联通，要选一个经过奇数次的点作为起点（根）。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FCC fclose(stdin),fclose(stdout)
const int INF = 0x3f3f3f3f,N = 1e5+10;
inline ll read()
{
	ll ret=0;char ch=' ',c=getchar();
	while(!(c>='0'&&c<='9')) ch=c,c=getchar();
	while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ch=='-'?-ret:ret;
}
int n,m,head[N],ecnt=-1,ans[N<<2],tot,w[N];
bool vis[N];
void init_edge(){memset(head,-1,sizeof(head)),ecnt=-1;}
struct edge
{
	int nxt,to;
}a[N<<1];
inline void add_edge(int x,int y)
{
	a[++ecnt]=(edge){head[x],y};
	head[x]=ecnt;
}
void dfs(int u,int fa)
{
	vis[u]=1,w[u]^=1,ans[++tot]=u;
	for(int i=head[u];~i;i=a[i].nxt)
	{
		int v=a[i].to;
		if(v==fa||vis[v]) continue;
		dfs(v,u);
		ans[++tot]=u;
		w[u]^=1;
	}
	if(w[u]) w[u]^=1,ans[++tot]=fa,w[fa]^=1,ans[++tot]=u; 
}
int main()
{
	init_edge();
	n=read(),m=read();
	for(int i=1;i<=m;i++)	
	{
		int u=read(),v=read();
		add_edge(u,v),add_edge(v,u);
	}
	int s=0;
	for(int i=1;i<=n;i++) 
	{
		w[i]=read();
		if(w[i]) s=i;
	}
	if(!s) return puts("0"),0;
//	printf("s=%d
",s);
	dfs(s,0);
	for(int i=1;i<=n;i++) 
		if(!vis[i]&&w[i]) return puts("-1"),0;
	
	if(ans[tot-1]==0&&tot>=3) tot-=3;
	printf("%d
",tot);
	for(int i=1;i<=tot;i++) printf("%d ",ans[i]);
	return 0;
}