题意

给定一张 $n$ 个点 $m$ 条边的无向图，边有 $0/1$ 边权和目标的 $0/1$ 边权。每次可以选取一个简单环，将环上的边权取反。求一个合法方案。$1\leq n\leq 10^5,1\leq m\leq 10^6$。

题解

之前做过但有点忘了，重做一下。

考虑 $s=t$ 的边，它们需要被经过偶数次，我们任取两个经过它的简单环，如果将该边删去，那完全可以把这两个简单环合并成一个，一定更优。于是只需要保留 $s\neq t$ 的边，DFS 找环，用栈记录方案。判无解等价于判断是否存在欧拉回路，即每个点都是偶度的。加上当前弧优化，时间复杂度为 $\mathcal{O}(n+m)$。

TLE 大概是当前弧写假了。

代码

#include <iostream>
#include <vector>

using namespace std;

#define lowbit(x) ((x) & -(x))
#define chk_min(x, v) (x) = min((x), (v))
#define chk_max(x, v) (x) = max((x), (v))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5, M = 2e6 + 5;

int n, m, k, deg[N], head[N];
int top, stk[N];
bool ve[M], in_stk[N], v[N];
vector<int> ans[M];

struct AdjList {
	int tot, head[N], nxt[M], to[M];
	void init() {
		tot = -1;
		for (int i = 1; i <= n; ++i) head[i] = -1;
	}
	void insert(int x, int y) {
		to[++tot] = y;
		nxt[tot] = head[x], head[x] = tot;
	}
} g;

void dfs(int x) {
	v[x] = 1;
	for (int &i = g.head[x]; ~i; i = g.nxt[i]) {
		if (ve[i]) continue;
		ve[i] = ve[i ^ 1] = 1;
		dfs(g.to[i]);
	}
	if (in_stk[x]) {
		ans[++k].push_back(x);
		while (top && stk[top] != x) {
			int y = stk[top--];
			ans[k].push_back(y), in_stk[y] = 0;
		}
		ans[k].push_back(x);
	} else in_stk[x] = 1, stk[++top] = x;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m, g.init();
    while (m--) {
    	int u, v, s, t; cin >> u >> v >> s >> t;
    	if (s == t) continue;
    	g.insert(u, v), g.insert(v, u);
    	++deg[u], ++deg[v];
	}
	for (int i = 1; i <= n; ++i) if (deg[i] & 1) return cout << "NIE", 0;
	for (int i = 1; i <= n; ++i) if (!v[i]) dfs(i);
	cout << k << '\n';
	for (int i = 1; i <= k; ++i) {
		cout << ans[i].size() - 1 << ' ';
		for (int j : ans[i]) cout << j << ' ';
		cout << '\n';
	}
    return 0;
}