二分图博弈
二分图博弈
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133840227
一张二分图，Alice和Bob每人走一步，不能重复走，谁不能走谁输
结论：若存在最大匹配不包含初始点，则Bob赢，否则Alice赢
以上图为例，红色为最大匹配。
首先对于Alice第一步只能走黑边。而Alice无论走到哪个点，都有一条红边。（不然就不是最大匹配了 ）
那么Bob就走红边，此时回到左边，Alice就只能走黑边了。
实现上，我们先把初始点去掉跑一遍流，加上后在残余网络上再跑一遍
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-15
奇偶博弈 + 二分图博弈：Gym 102832H
奇偶博弈 + 二分图博弈：Gym 102832H 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133840132 https://vjudge.net/contest/587311#problem/I 赛时想了好久，啥都没想到 博弈，在你啥都想不到时，就硬上套路。赛时想了好久假设法，但就是发了奇偶博弈。 从奇偶角度考虑。每转一位会使这一位的奇偶性改变，也会使和的奇偶性改变。 然后关键地方到了，发现Alice和Bob操作的奇偶性永远不变，也就是形成了一个 ...
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-10-11
点向行列连边的网络流图优化成行列连边的二分图：CF1592F2
点向行列连边的网络流图优化成行列连边的二分图：CF1592F2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133764633 https://www.luogu.com.cn/problem/CF1592F2 做完F1，然后用1的结论来思考。 场上推了几个性质。首先op4的操作行列必然两两不同，所以op4最多 max(n,m)\max(n,m)max(n,m) 次。然后手玩发现只有除 (n,m)(n,m)(n,m) 的三个格子都为1，op4才有意义。 ...
2023-09-16
二分套网络流：ABC320G
二分套网络流：ABC320G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132927159 首先肯定先枚举数字 然后考虑二分答案 每个字符串向它合法的位置连边 然后易发现每个点出度最多为 nnn ，不然没意义 所以最多 O(n2)O(n^2)O(n2) 条边 然后跑网络流，看能不能流完，也就是能不能匹配成功即可 123456789101112131415161718192021222324252627282930313233343536373839404...
2023-12-19
坐标前后限制转点的坐标取值+网络流拆维拆点：agc031_e
坐标前后限制转点的坐标取值+网络流拆维拆点：agc031_e 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135075877 https://vj.imken.moe/contest/598718#problem/J 观察到数据范围很小，但一个很重要的信息我们缺失了，就是珠宝的数量，所以我们考虑枚举珠宝的数量 kkk 。 对于横纵坐标什么至多至少的限制，比如 aia_iai 前最多偷 bib_ibi 个，可以转化为第 [bi+1,k][b_i+1,k]...
2023-09-16
atcoder库中的网络流用法
atcoder库中的网络流用法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132643984 头文件： 12#include<atcoder/all>using namespace atcoder; 定义： 1mf_graph<int>G(N); //N为边数 连边： 1G.add_edge(u,v,w); //u->v容量为w 最大流： 1int maxflow = G.flow(S,T,1e9); //从S流向T，初始...