最小割构造
最小割构造
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134750195
考虑跑完最大流，我们再从源点跑一遍bfs，所以能跑到的点都属于点集A，否则属于点集B
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
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 就是个最小割 发现我们可能要割很多次，我们可以直接建分层图，在分层图上完成
2026-09-06
状压dp + 最小割中inf双向单向变的捆绑决定技巧：ABC472G
状压dp + 最小割中inf双向单向变的捆绑决定技巧：ABC472G 法1：状压dp 首先本质上每一行都是可以抽象成连续段，连续段数量不超过15，所以每一维的状态可以直接存下来。 设 dp[i][S]dp[i][S]dp[i][S] 代表第 iii 行的状态为 SSS 时，前 iii 行的最大值。 显然对于一个固定的 SSS，可以很轻松求出下一行对应的 S′S'S′，因此转移到 dp[i+1][S′]dp[i+1][S']dp[i+1][S′]。 而现在考虑新的一行的内部，可以新增#段。也就是让 dp[i+1][S]dp[i+1][S]dp[i+1][S] 贡献到 d...
2023-12-19
考虑全选然后删的代价转最小割+最小割同一类连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 理论上界为 ∑∣bi∣\sum |b_i|∑∣bi∣ 。考虑现在减少会有什么情况： 不选。代价为 ai+∣bi∣a_i+|b_i|ai+∣bi∣ 原先为正，所在连通块取绝对值后变负。代价为 −2∣bi∣-2|b_...
2023-10-24
分析性质+排列置换环+最小割：1024T4
分析性质+排列置换环+最小割：1024T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134022318 http://cplusoj.com/d/senior/p/SS231024D 相当于各选一些置换环进行一次位移 我们考虑只对A进行置换。对于一个大小>1的环，如果对其进行位移，一定可以使这些位完全不同。 因此，如果我们置换B，置换的意义是什么？是把A中自环的位置统计掉，使这些位置不同。 但如果我们再置换B，可能会和之前已经置换的A在某些地方相...
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
每个点取值拆成多个点的最小割问题：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+...