考虑全选然后删的代价转最小割+最小割同一类连inf的边：AT_arc107_f
考虑全选然后删的代价转最小割+最小割同一类连inf的边：AT_arc107_f
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135093630
https://www.luogu.com.cn/problem/AT_arc107_f
理论上界为 。考虑现在减少会有什么情况：
-
不选。代价为
-
原先为正，所在连通块取绝对值后变负。代价为
-
原先为负，所在连通块取绝对值后变正。代价为
有一堆代价，很容易想到流 / 割。
然后每个联通块有两种取值（正 / 负），正好对应源汇点，因为是归类，所以是割。
至于第一种情况，因为只和自已有关，显然拆点连边。
现在还有一个问题，同一个联通块必须同号。转化一下是什么，有边相连的点必须归类到同源同汇（也就是归类到同一边）。经典套路，连一条反向无穷大的边即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-06
充分理清限制与条件+构造二分图+最小割：ARC142E
充分理清限制与条件+构造二分图+最小割：ARC142E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133623334 https://www.luogu.com.cn/problem/AT_arc142_e 他的充要条件是是什么： ai,aj≥min(bi,bj)a_i,a_j\ge min(b_i,b_j)ai,aj≥min(bi,bj) 存在 ai≥max(bi,bj)a_i\ge max(b_i,b_j)ai≥max(bi,b...
2023-12-02
最小割构造
最小割构造 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134750195 考虑跑完最大流，我们再从源点跑一遍bfs，所以能跑到的点都属于点集A，否则属于点集B
2023-12-11
1211T2：分层图跑最小割（要割几次的最小割）
1211T2：分层图跑最小割（要割几次的最小割） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134926699 http://47.92.197.167:5283/contest/437/problem/2 k=1k=1k=1 就是个最小割 发现我们可能要割很多次，我们可以直接建分层图，在分层图上完成
2023-12-20
平面图转对偶图 + 平面图上最小割转对偶图上最短路
平面图转对偶图 + 平面图上最小割转对偶图上最短路 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135111564 如上图所示，有一个平面图，有很多点组成，每个接触线有一个权值。我们可以把平面图转成对偶图。我们在 (s,t)(s,t)(s,t) 之间画一条直线，把外面分成两个面。我们把每个面视为一个点。如果两个面有接触线，他们就连一条边，边的边权，就是接触线的边权。 在上图上，如如果我们想求 s→ts\to ts→t 的最大流，根据最大流 = 最小割，我...
2023-12-18
把状态拆成长链来跑网络流（转化为最小割）：LibreOJ - 2384
把状态拆成长链来跑网络流（转化为最小割）：LibreOJ - 2384 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135058691 https://vj.imken.moe/contest/598718#problem/C 一个点要确定一个取值，然后每个取值还有代价，我们就拆成一条链： 源汇点就可以连对应代价的差分 然后题目肯定有某些一堆限制，关于某两条链的取值有什么限制，我们就可以在链之间连很多很多无穷的边来解决，比如： 这就代表如果第一条链 ≥...
2023-12-02
每个点取值拆成多个点的最小割问题：CF1430G
每个点取值拆成多个点的最小割问题：CF1430G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134751924 https://vj.imken.moe/contest/597216#problem/I 题目等价于求 min∑uau(outu−inu)\min \sum_{u}a_u(out_u-in_u)min∑uau(outu−inu) 发现每个数的取值范围最多到 nnn ，然后又有一堆限制，考虑拆点+网络流。 每个点拆成 n+2n+2n+...