自动搬运

查看原文

来自洛谷，原作者为

	irris Good Luck.

搬运于2025-08-24 23:09:10，当前版本为作者最后更新于2025-02-01 18:27:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

鲜花

所以为什么数据范围是 $n, m \leq 2\times 10^4$，明明可以做到 $\mathcal O(n + m)$ 啊？

题解

假如选出了一些无向边，并且钦定了它们的方向，这时，为了形成一条欧拉回路，边集合法当且仅当

• 边集是连通的；
• 每个点的入度等于出度。

对于 $m$ 条有向边，初始先让 $d_i = \sum\limits_{i \to v} 1 - \sum\limits_{v \to i} 1$（即出度减入度）。我们的目标是 $d_i = 0$。

考虑一棵树怎么做。注意到对于一片叶子 $u$，与它关联的边只有一条 $(u, v)$，而这条边的不被选择 / 被选择且定向 $u \to v$ / 被选择且定向 $v \to u$ 三种操作对 $d_u$ 的影响互不相同，于是这条边最终的状态可以确定（如果无论如何 $d_u$ 都不能为 $0$，则一定无解）。确定完这条边的状态即可删掉这条边，所以最后的过程形如拓扑排序，我们可以唯一确定选出的边集和每条边的方向，只需检验是否连通即可。

对于基环树，枚举环上一条边的状态即可转化为树。

参考实现

using pii = std::pair<int, int>;
const int INF = 0x3f3f3f3f;

#define MAXN 20001
std::vector<int> g[MAXN];
int deg[MAXN], deg2[MAXN], vis[MAXN], d[MAXN];

int fa[MAXN], fa2[MAXN];
inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int solve(int n, std::vector<int> c, const std::vector<int> &r, int t = 0) {
	int ans = 0;
	for (int i = 1; i <= n; ++i) fa[i] = fa2[i];
	if (t) fa[find(c[0])] = find(c.back());
	for (int i = 1, n = c.size(); i < n; ++i) {
		if (std::abs(c[i - 1]) > 1) return INF;
		ans += std::abs(c[i - 1]), c[i] += c[i - 1];
		if (c[i - 1] != 0) fa[find(r[i])] = find(r[i - 1]);
		if (i == n - 1 && c[i] != 0) ans = INF; 
	}
	int con = -1;
	for (int i = 1; i <= n; ++i) if (d[i]) {
		if (con == -1) con = find(i);
		else if (find(i) != con) return INF;
	}
	return ans;
}
int main() {
	int n = read<int>(), m = read<int>(), res = m;
	for (int i = 1, u, v; i <= n; ++i) {
		u = read<int>(), v = read<int>();
		g[u].push_back(v), g[v].push_back(u);
		++deg[u], ++deg[v];
	}
	for (int i = 1; i <= n; ++i) fa[i] = i;
	for (int i = 1, u, v; i <= m; ++i) {
		u = read<int>(), v = read<int>();
		++deg2[u], --deg2[v], fa[find(u)] = find(v), d[u] = d[v] = 1;
	}
	std::queue<int> q;
	for (int i = 1; i <= n; ++i) if (deg[i] == 1) q.push(i);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (std::abs(deg2[u]) > 1) return puts("-1"), 0;
		res += std::abs(deg2[u]), vis[u] = 1;
		for (int v : g[u]) if (!vis[v]) {
			deg2[v] += deg2[u];
			if (deg2[u] != 0) fa[find(u)] = find(v);
			if ((--deg[v]) == 1) q.push(v);
		}
	}
	for (int i = 1; i <= n; ++i) fa2[i] = fa[i];
	std::vector<int> cyc, r;
	for (int i = 1; i <= n; ++i) if (!vis[i]) {
		int u = i;
		while (!vis[u]) {
			cyc.push_back(u), vis[u] = 1;
			for (int v : g[u]) if (!vis[v]) 
				{ u = v; break; }
		}
		r = cyc;
		for (int &u : cyc) u = deg2[u];
		int k = cyc.size(), t = solve(n, cyc, r);
		cyc[0] += 1, cyc[k - 1] -= 1, t = std::min(t, solve(n, cyc, r, 1) + 1);
		cyc[0] -= 2, cyc[k - 1] += 2, t = std::min(t, solve(n, cyc, r, 1) + 1);
		if (t >= INF) res = -1; else res += t;
	}
	print<int>(res, '\n');
	return 0;
}