自动搬运

查看原文

来自洛谷，原作者为

	Cwkapn 一定要在不远的将来，赶上和超过世界先进水平

搬运于2025-08-24 23:17:06，当前版本为作者最后更新于2025-07-05 15:55:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目分析

首先注意到，可以将颜色看成结点，盒子中上方球的颜色和下方球的颜色之间连边，这样就可以将盒子中的球上下关系转化为一张图。图中有若干连通块，每个块内的颜色球移动不影响块外的球答案（因为块内的颜色和块外不需要也不能进行移动）。所以考虑分别处理每个连通块。下文中，符合要求是指每种颜色的两个球都在同一个盒子中。

可以发现，想要让块内颜色球位置符合要求，需要先将某两种颜色球移动到空盒（$2$ 步），再将其它颜色球依次配对（每种颜色需要 $1$ 步），最后空出一个盒子。因此，若一个连通块内有 $x$ 种颜色且可以符合要求，让它们符合要求需要：

• $0$ 步，如果 $x=1$（本来就是符合要求的）；
• $x + 1$ 步，如果 $x>1$。

现在考虑验证某个块通过移动符合要求可行性的方法。注意到只有 $1$ 个空盒，所以同一时间最多转移出 $2$ 个球。因此，考虑设第 $i$ 种颜色球在上方的盒子数 $u_i$。根据题意，$u_i$ 的取值为 $0,1$ 和 $2$。如果一个连通块内存在 $2$ 种颜色的 $u_i=2$，则只用一个空盒无法完成移动。可以基于这个特性对连通块进行验证。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, a[N][5];
int fa[N];
int getfa(int x) {return (x == fa[x]) ? x : (fa[x] = getfa(fa[x]));}
void merge(int x, int y) {
	x = getfa(x), y = getfa(y);
	if (x != y) fa[x] = y;	
}
int cnt[N];
vector<int> g[N];
int up[N], pos[N][5];
bool nok(int x) { // 判断连通块是否不符合要求
	int flag = 0;
	for (int i = 0; i < g[x].size(); i++) {
		if (up[g[x][i]] == 2) {
			if (flag) return true;
			flag = g[x][i];
		}
	}
	return false;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= n; i++) {
		cin >> a[i][1] >> a[i][2];
		merge(a[i][1], a[i][2]);
		up[a[i][1]]++;
		pos[a[i][1]][1 + (pos[a[i][1]][1] != 0)] = i;
	}
	for (int i = 1; i <= n; i++) {
		int tmp = getfa(i);
		cnt[tmp]++;
		g[tmp].push_back(i);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (cnt[i] == 0 || cnt[i] == 1) continue;
		if (nok(i)) {
			cout << -1 << '\n';
			return 0;
		}
		ans += cnt[i] + 1; 
	}
	cout << ans << '\n';
	return 0;
}