题解：P12026 [USACO25OPEN] Compatible Pairs S

题目链接

https://www.luogu.com.cn/problem/P12026

算法 & 数据结构

图论，拓扑排序，建图。

思路

Subtask 1

这个 Subtask 是 $A = B$。

我们首先想到建立一个图，每个 ID 号码为一个点，如果有一个 ID 的牛可以和另一个 ID 的牛交流，那么我们建立一个从第一个 ID 到第二个 ID 的边。

因为题目定义，所以如果一个 ID 可以和另外一个 ID 交流，另外一个 ID 也可以和这个 ID 交流。

由于 $A = B$，那么每一个 ID 最多存在一个 ID 可以交流，所以一共有很多独立的 ID 对，每个 ID 对的两个 ID 可以互相交流。

答案就是统计一下每个 ID 对就行了。

满分

我们假定 $A \not = B$，因为 $A = B$ 的情况分析过了。

由于一个点的度数最多为 $2$，那么只有可能是一个环或者一个链加一堆自环。

可以通过假设一个点是 $x$，然后根据一个边上的两点的和是 $A$ 或 $B$ 来证明不可能存在环。

那么只有可能是一个链加一堆自环了，可以用拓扑排序，然后计算。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, a, b;
int d[1000005], m[1000005], con[1000005], ans, c[1000005], su[1000005], in[1000005], vis[1000005];
vector <int> e[200005];
map <int, int> mp, mi;

signed main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i ++) {
        cin >> m[i] >> d[i];
        mp[d[i]] += m[i];
        mi[d[i]] = i;
    }
    for (int i = 1; i <= n; i ++) {
        if (mp[a - d[i]]) {

            e[i].push_back(mi[a - d[i]]);
            in[mi[a - d[i]]] ++;
        }
        if (mp[b - d[i]] && a - d[i] != b - d[i]) {

            if (a - d[i] != b - d[i]) e[i].push_back(mi[b - d[i]]), in[mi[b - d[i]]] ++;
        } 
    }

    queue <int> q;
    for (int i = 1; i <= n; i ++) if (in[i] == 1) q.push(i);
    while (q.size()) {
        int nw = q.front();
        q.pop();
        for (auto x : e[nw]) {
            if (vis[x]) continue;
            if (x == nw) ans += m[x] / 2, m[x] %= 2;
            else {
                int tmp = min(m[nw], m[x]);
                ans += tmp;
                m[x] -= tmp;
                m[nw] -= tmp;
            }
            if (-- in[x] == 1) q.push(x);
        }
        vis[nw] = 1;
    }
    cout << ans;
    return 0;
}