题目链接
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;
}