RainAir
My OI Blog
RainAir
「POJ1966」Cable TV Network

题目链接

题目描述

给定一张无向图,求让这张无向图不连通应删去的点的最小个数。
https://blog.aor.sd.cn/wp-content/uploads/2018/12/06f2a8b29ab8c13bc8f4fc34a5e4ffe4.jpg

解题报告

首先发现这很像割的定义,只不过由边转化为了点。
那我们不妨拆点来对边进行限制:其中对于每个点 $v$ 拆成 $v$ 和 $v’$ ,然后我们在这两个点之间连一条容量为 $1$ 的边,然后原图边容量为 $INF$ ,用最大流最小割定理求解即可。
但是我们发现题目里没有给出源点和汇点,直接的想法是枚举,但是我们其实可以固定一个源点,只枚举汇点就可以了,最后对于每一次的最大流都取个最小值就可以了。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/388
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「POJ1966」Cable TV Network
题目链接 题目描述 给定一张无向图,求让这张无向图不连通应删去的点的最小个数。 解题报告 首先发现这很像割的定义,只不过由边转化为了点。 那我们不妨拆点来对边进行限制:其中对…
扫描二维码继续阅读
2018-12-24
标签
近期评论