题解: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;
}
本文链接:https://ztrztr.top/archives/973
版权声明:本文 《题解:P12026 [USACO25OPEN] Compatible Pairs S》 为 ztrztr 原创。著作权归作者所有。
转载说明:联系作者或者评论区留言获得转载授权,并注明转载地址。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇