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

Cwkapn · 2025-07-05 15:55:26 · 题解

题目分析

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

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

现在考虑验证某个块通过移动符合要求可行性的方法。注意到只有 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;
}