题解 CF453C 【Little Pony and Summer Sun Celebration】

发表于 | 更新于

$Desciption$

给一个无向图$,n$个点$m$条边，给定一个$01$序列，如果$a[i]=1,$要求走到这个点奇数次$,$否则，要求走到这个点偶数次$,$请你任选起点$,$输出满足要求的经过点的序列和序列长度$,$序列长度不能超过$4n$

$Solution$

先判断是否有解，如果图不连通，且两个块中都有要求走过奇数次的点，就无解。

我们可以将$a$序列作为初始状态，每经过一次$i$号点，相当于$a[i]~\hat{}=1,$目标是使$a$序列全部变成$0$

选定一个要求走过奇数次的点作为$root,$每个点只走一次，最后回到$root,$那么走过的就是一棵树。

走的路程就相当于对这棵树进行$dfs$遍历，注意:回溯的过程也算一次经过.
所以叶子节点只经过一次，其它节点经过$($儿子数量$+1)$次,

对于一个点，在回溯时，如果$a[i]$还是1，就要进行震荡操作，震荡操作是指对于点$i$回溯到$fa[i]$时，从$fa[i]$走到$i$再走回$fa[i]$的过程，经过这一操作，效果是$a[i]~\hat{}=1,a[fa[i]]~\hat{}=1$

如果$root$需要震荡,我们可以不回溯到$root$，这样就相当于$a[root]^=1$

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define re register
#define N 405400
#define mod 1000000007
using namespace std;
struct edge{
    int to,next;
}e[N];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int s,ans[N],vis[N],tot,d[N],n,m,head[N],cnt;
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa){
    ans[++tot]=u;vis[u]=1;d[u]^=1;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (vis[v])continue;
        dfs(v,u);ans[++tot]=u;d[u]^=1;
    }
    if (d[u]){
        ans[++tot]=fa;ans[++tot]=u;d[fa]^=1;d[u]^=1;
    }
}
signed main(){
    n=read(),m=read();
    for (int i=1;i<=m;++i){
        int u=read(),v=read();
        add(u,v);add(v,u);
    }
    for (int i=1;i<=n;++i){
        d[i]=read();if (d[i])s=i;
    }
    dfs(s,0);
    for (int i=1;i<=n;++i)
        if (d[i]){
            puts("-1");return 0;
        }
    if (tot>1&&!ans[tot-1])tot-=3;
    printf("%d\n",tot);
    for (int i=1;i<=tot;++i)printf("%d ",ans[i]);
    return 0;
}