【链接】点击打开链接

【题意】

给出一个连通图，并给每个点赋一个d值0或1或-1,要求选出一个边的集合，使得所有的点i要么d[i] == -1,要么 dgree[i] % 2 == d[i]，dgree[i]代表i结点的度数。

【题解】

先统计出所有点所要求的度数的和cnt1。(不考虑-1);

这里的cnt1的奇偶性也就是最后的图的所有点的度数和的奇偶性.

显然只要是一张图,它的所有的度数的和就必须为偶数。

所以,如果cnt1是个奇数,且没有为-1的点,那么直接输出-1就好,无解.

如果有-1的话,那么显然我们是可以把它凑成偶数的。

这样把所有的-1都改成0或1,然后满足n个点的度数和为偶数就好了。

度数和为偶数之后,我们从任意一个点开始进行dfs.

我们可以考虑它任意的一个生成树。(其他地方不加边)

(不加任何边也算是偶数!)

然后从树的叶子节点往上处理。

(我们接下来的任务就是维护所有节点的度数之和总为偶数)

对于当前节点cur.

如果d[cur]==0,则跳过cur和parent[cur]之间的边.不做处理,则度数之和不变还是偶数.

如果d[cur]==1,则把cur和parent[cur]之间的边加到ans里面去,同时把d[parent[cur]]取反,也即0变成1,1变成0,然后d[cur]变成0.这样做,我们把d[cur]的奇偶性变了一下,然后d[parent[cur]]的奇偶性也变了.则度数之和的奇偶性还是不变,仍然为偶数。

同时d[cur]变为0,表示cur这个点不需要边了,然后d[cur的父节点]的奇偶性改变的话,表示cur的父亲节点需不需要边的状态也改变了。

我们最后的目标,显然是让所有的d[cur]都变成0,也即所有的点都不需要边了。

而我们的操作能时刻保证,所有的d值的和都为偶数,则根节点进行操作完之后,所有d的值的和仍然为偶数。

而根节点以下的所有点的值都变成了0,根节点的d值为0或为1，那么也就是说根节点的d值也变成了0。

这就说明可以让所有的d值都为0.

输出加入的边就好。

【错的次数】

【反思】

图的点的度数之和总是一个偶数的。

用生成树来简化图的问题。

只要度数之和为偶数.(只要求每个点的度数的奇偶性)那么一定有解。

【代码】

/*

*/

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <map>

#include <queue>

#include <iomanip>

#include <set>

#include <cstdlib>

#include <cmath>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb emplace_back

#define fi first

#define se second

#define ld long double

#define ms(x,y) memset(x,y,sizeof x)

#define ri(x) scanf("%d",&x)

#define rl(x) scanf("%lld",&x)

#define rs(x) scanf("%s",x)

#define rf(x) scnaf("%lf",&x)

#define oi(x) printf("%d",x)

#define ol(x) printf("%lld",x)

#define oc putchar(' ')

#define os(x) printf(x)

#define all(x) x.begin(),x.end()

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

#define sz(x) ((int) x.size())

#define ld long double

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

//mt19937 myrand(time(0));

//int get_rand(int n){return myrand()%n + 1;}

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 3e5;

int n, m,d[N+10],cnt1,cnt0;

bool bo[N + 10];

vector <pii> g[N + 10];

vector <int> ans;

void dfs(int x) {

	bo[x] = true;

	for (pii temp : g[x]) {

		int y = temp.first, id = temp.second;

		if (!bo[y]) {

			dfs(y);

			if (d[y] == 1) {

				d[x] ^= 1;

				d[y] = 0;

				ans.pb(id);

			}

		}

	}

}

int main() {

	//Open();

	//Close();

	ri(n), ri(m);

	rep1(i, 1, n) {

		ri(d[i]);

		if (d[i] == 1) cnt1++;

		if (d[i] == -1) cnt0++;

	}

	rep1(i, 1, m) {

		int x, y;

		ri(x), ri(y);

		g[x].pb(mp(y,i)), g[y].pb(mp(x,i));

	}

	if ((cnt1 & 1) && cnt0 == 0) {

		puts("-1");

		return 0;

	}

	cnt1 = cnt1 & 1;

	rep1(i,1,n)

		if (d[i] == -1) {

			d[i] = cnt1;

			cnt1 = 0;

		}

	dfs(1);

	oi(sz(ans)); puts("");

	for (int x : ans)

		oi(x), puts("");

	return 0;

}

巴特西

【Codeforces Round #429 (Div. 1) B】Leha and another game about graph