题解：P12649 [KOI 2024 Round 2] 收集彩球

先多尝试几个例子，可以发现同一个盒子中，球和球之间其实是两两限制的关系。我们习惯用图来刻画这种限制关系，考虑对同一个盒子中上方球的颜色向下方球的颜色连一条有向边，这样我们可以得到若干连通块。

不难发现每个连通块之间互不关联，因为如果两个点不在同一个连通块中就说明它们的颜色没有互相限制。所以不妨对每个连通块单独考虑。

然后我们想一下如果要把某一个大小为

cnt

的连通块中的颜色归位需要的操作次数，大体分为两步：

把某个颜色的两个位于上层的球移动到空盒，解放位于下层的球，需要 $2$ 步操作。
把被解放的下层球移动到存在与其颜色相同的球的盒子上层，每种颜色都需要 $1$ 次操作，除去操作一还剩 $cnt-1$ 种颜色未归位，所以总共需要 $cnt-1$ 步操作。

综上，操作次数为

2+(cnt-1)=cnt+1

。（别忘了特判自环的情况，答案为

0

。）

再考虑有解判定，因为只有一个用来中转的空盒，所以大胆猜测如果同种颜色的球都在上层的颜色超过一个，空盒就不够了，无解。

证明：因为每种颜色的球都只有两个，所以除了第一次移到空盒外，之后操作中不会再出现空盒，没有空盒就无法把都在上层的颜色归位，于是无解。

放在图上，就是如果入度为

0

的点超过一个，则无解。

因为真正跑图的时候只要统计出每个连通块（弱联通分量）中点的个数和其中入度为

0

的点数，考虑在建边的时候直接建无向图，跑起来方便一些。

O(n)

。

CPP

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;

int n, d[maxn], vis[maxn];
vector<int> G[maxn];

int cnt1, cnt2; // 统计点数、入度为0的点个数
void dfs(int u){
	if(vis[u]) return ;
	vis[u] = 1;
	cnt1 ++;
	cnt2 += (d[u] == 0);
	for(int v : G[u]) dfs(v);
}

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; i ++){
		int a, b; cin >> a >> b;
		G[a].push_back(b); G[b].push_back(a);
		d[b] ++; // 注意统计的还是有向图的入度
	}
	int ans = 0;
	for(int i = 1; i <= n; i ++){
		if(!vis[i]){
			cnt1 = 0, cnt2 = 0;
			dfs(i);
			if(cnt2 > 1){ cout << "-1\n"; return ; } // 无解
			if(cnt1 != 1) ans += cnt1 + 1; // 判不是自环
		}
	}
	cout << ans << '\n';
}

signed main()
{
	ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	solve();
	return 0;
}

题解：P12649 [KOI 2024 Round 2] 收集彩球

文章操作

相关推荐

评论

题解：P12649 [KOI 2024 Round 2] 收集彩球