P4589 [TJOI2018]智力竞赛(上下界网络流)-白红宇的个人博客

P4589 [TJOI2018]智力竞赛(上下界网络流)

发布日期：2021-06-30 10:31:53 浏览次数：2 分类：技术文章

本文共 378 字，大约阅读时间需要 1 分钟。

用有源汇上下界可行流就是裸题了,简单说一下

建立源点 $s$ 连向虚点 $x u$ ,流量为 $[0, n + 1]$ ,表示只能答题 $n + 1$ 次

把一个人拆分为 $u$ 和 $u + m$ ,如果必须要经过这个人流量是 $[1, n + 1]$ ,否则是 $[0, n + 1]$

然后 $x u$ 连向 $u$ 流量为 $[0, n + 1]$ ,表示可以走任意次

$u + m$ 连向 $t$ 流量 $[0, n + 1]$ ,表示可以在这里停下来任意次

按照套路判断是否可行即可。

还有一种做法,跑最小可重覆盖链,这个可以看题解

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115426771 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：P4194 矩阵(二分+有源汇可行流)

下一篇：CF277E Binary Tree on Plane(二叉树::二分图匹配)

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！