Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

CF840B Leha and another game about graph

Posted on

又是CF的神仙图论度数构造题。

Solution

首先考虑无解的情况，考虑到每条边无论选不选最后对于点的度数的影响一定是成偶数的（一条边有两个端点），所以当一个连通块其中的点的度数之和无论如何都是奇数时，一定无解，不难发现当一个连通块存在-1时怎么也不可能是无解，所以只需判断是否存在-1或者度数之和是否为偶数即可判断有无解。

紧接着来考虑怎么构造出一组合法方案，考虑到爆搜的实现性极差，我们首先建立一颗生成树（随机的），如果某个点和其子树的点权和为奇数，则加上与父亲的边，否则断掉（遇到-1直接断掉）。

注意到我们这是在将问题由子树向根节点转移，所以根节点需要是-1（这样才可能应对子树的各种情况），当然，当不存在-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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
#define PII pair<int, LL>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
	while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
	if(flag) res = -res; 
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
	if(res < 0) putchar('-'), res = -res;
	if(res > 9) write(res / 10);
	putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); } 
const int N = 3e5 + 5;
int n, m;
int a[N];
int ans[N << 1], cnt;
bool vis[N];
int idx = 1;
int e[N << 1], ne[N << 1], h[N];
inline void add(int x, int y)
{
    idx ++;
    e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
bool dfs(int x)
{
    vis[x] = 1;
    bool res = a[x];
    for(int i = h[x], j; ~i;i = ne[i])
    {
        j = e[i];
        if(vis[j]) continue;
        if(dfs(j)) ans[++ cnt] = i / 2, res ^= 1;
    }
    if(a[x] == -1) res = 0;
    return res;
}
int main()
{
    memset(h, -1, sizeof(h));
    read(n, m);
    int id = 0, flag = 0;
    for(int i = 1;i <= n;i ++)
    {
        read(a[i]);
        if(a[i] == -1) id = i;
        else flag ^= a[i];
    }
    for(int i = 1, o, u;i <= m;i ++) read(o, u), add(o, u), add(u, o);
    if(!id && flag) return puts("-1"), 0;
    id = max(id, 1);
    dfs(id);
    write(cnt, '\n');
    sort(ans + 1, ans + cnt + 1);
    for(int i = 1;i <= cnt;i ++) write(ans[i], '\n');
    return 0;
}