阴阳反转——运用INF巧妙建网络流：P3980
阴阳反转——运用INF巧妙建网络流：P3980
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080814
https://vj.imken.moe/contest/598718#problem/L
考虑一个奇妙的转化：
有很多 个人要走 扇门，第 扇只能走 个人，有 个通道，可以把一个人从 运到 ，但要给 的钱，求所有人到达终点的最小代价。
然后直接流即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
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-12-19
通过费用流中的贪心来保证计数正确性：P4249剪刀石头布
通过费用流中的贪心来保证计数正确性：P4249剪刀石头布 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080431 https://vj.imken.moe/contest/598718#problem/K 三元环数量尽量多，也就是非三元环数量尽可能少。非三元环的充要条件是存在一个点度数为2，而每条边可以给一个点一个度数，然后就变成了经典网络流问题。 但是，对于一个点，我们还是无法求最少流。考虑转化为费用流。一个点向汇点连很多条边，分别代表着度数为1...
2023-09-16
二分套网络流：ABC320G
二分套网络流：ABC320G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132927159 首先肯定先枚举数字 然后考虑二分答案 每个字符串向它合法的位置连边 然后易发现每个点出度最多为 nnn ，不然没意义 所以最多 O(n2)O(n^2)O(n2) 条边 然后跑网络流，看能不能流完，也就是能不能匹配成功即可 123456789101112131415161718192021222324252627282930313233343536373839404...
2023-11-14
缩点+图论路径网络流：1114T4
缩点+图论路径网络流：1114T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134407471 http://cplusoj.com/d/senior/p/SS231114D 重新梳理一下题目 我们先建图 x→yx\to yx→y ，然后对点分类：原串出现点，原串未出现点。 假如我们对一个原串出现点进行了操作，那么它剩余所有出边我们立刻去操作必然没有影响。所以我们只要所有原串出现点都操作一遍即可（如果有出边），那么我们就把边问题变成了点问题。 考虑一次...
2023-09-02
利用网络流通过拆点判断图的路径存在性问题：abc318_g
利用网络流通过拆点判断图的路径存在性问题：abc318_g 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132644032 https://atcoder.jp/contests/abc318/tasks/abc318_g 对于图上一类路径是否存在问题，可以考虑网络流。 Trick1 路径存在转网络流 题目转化为： 找出两条不交路径 B->A, B->C 对于已经找到的路径，我们 不能再走 。对于当前我们找到的某条路径，我们可能进行 反悔 ...
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...