Compatible Pairs (USACO Silver 2025 Open)

建图，加起来是A或B的结点之间加边，自己加自己是A或B的节点加自环。然后我们发现除了自环之外，这个图没有其它环。

而最优解就是从叶子节点开始去掉节点，每次去掉的时候就输出通信对数，加起来就是最终结果。

为什么从叶子节点开始生成结果更优？考虑以下的情况：

 A = 3, B = 5

 3 ---- 2 ---- 1 ---- 4
(10)   (10)   (10)   (10)

1、2、3、4这4个ID各有10头牛，建出来的图是一个串串。这个时候，2-3和1-4分别匹配，则结果是20。如果3和1匹配，则结果是10。所以从两端（叶子）节点开始匹配，肯定结果是更优的。

所以用类似拓扑排序的算法，每次去掉叶子节点（度为1的节点）就可以了，维护一个度为1的节点的队列。

这个题主要是要想到建图的办法，我一开始想从局部关系枚举所有可能性，后来发现那个办法是错的。能够转换成图的时候，一般都能够把数据之间的关系展示的更清楚，所以能放到图上的做的题，优先考虑图的解法。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int N,A,B;
map<int,int> m;
map<int,set<int>> adj;
queue<int> q;
 
void add_edge(int u, int v) {
    if (m[u] == 0 || m[v] == 0) return;
    adj[u].insert(v);
    if (u != v) adj[v].insert(u);   // self loop
}
 
int main() {
    scanf("%d%d%d", &N, &A, &B);    
    for (int i = 0; i < N; i++) {
        int n,d;
        scanf("%d %d", &n, &d);
        m[d]=n;
    }
    for (auto [d,n]: m) {
        add_edge(d, A-d);
        if (B != A) add_edge(d, B-d);
    }
    for (auto [d,n]: m) {
        if (n && adj[d].size() == 1) 
            q.push(d);
    }
    ll ans = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();
        if (adj[u].size() == 0) continue;
        int v = *adj[u].begin();
        int r = u != v ? min(m[u], m[v]) : m[u] / 2;
        ans += r;
        m[u] -= r;
        adj[u].erase(v);
        if (u != v) {   // not self loop
            m[v] -= r;
            adj[v].erase(u);
            if (adj[v].size() == 1) q.push(v);
        }
    }
    printf("%lld\n", ans);
    return 0;
}