CF903G Yet Another Maxflow Problem
2700
关键点：最大流转最小割
显然我们需要用其他方式维护最大流，考虑到最大流等于最小割，于是我们去求最小割。
考虑这个图的特性不难发现左边和右边两列都至多割掉一条边，于是我们直接枚举割掉的位置，剩下的左边前缀和右边后缀所有相连的边都要割。
考虑维护，我们从小到大枚举左边，于是答案由右边确定，用线段树维护，每次加入一条连接两边的边就将右边的一段前缀加上这条边的容量即可。
由于只会修改左边，我们预处理完后再用线段树维护左边单点修改即可。
CF1082G Petya and Graph
2400
关键点：最大权闭合子图
二分图，左边是边，右边是点，然后最大权闭合子图即可。难度虚高，现在已经烂透了。
CF1263F Economic Difficulties
2400
关键点：闭合子图，最小割，虚树
首先这题相当于划分两个集合，虚树大小之和最小，用虚树经典结论 dfs 序排序后两两距离之和配合 dp \(O(n^2)\) 完事儿。有点套路。
但是网络流解法很神！
观察性质：每条边实际上管辖了一个 dfs 序区间，并且每个区间都是唯一的，如果不同树上的两个边的区间有交集，那么这两条边必须保留一个！！！
于是我们将必须保留一个的边之间连边，变成求二分图最小点覆盖。
如何证明求出的方案合法？考虑到这将是一个比较神奇的结构，管辖一个点的所有边两两连边，并且分别互相包含，这意味这我们可以调整使其全部再同一棵树上被选中。
于是我们可以二分图最小点覆盖来求，时间复杂度 \(O(n^{2.5})\) 但是跑不满。
第一种解法：提交记录
CF277E Binary Tree on Plane
2400
关键点：二分图匹配，费用流
没啥意思，二分图，如果 \(a\) 可以做 \(b\) 儿子就从左往右连边，左边容量为 1，右边容量为 2 即可。
CF717G Underfail
2400
关键点：费用流，神仙建模
CF1198E Rectangle Painting 2
2500
关键点：性质，最小点覆盖
首先观察不难发现，每次取一行或一列肯定是最好的。
棋盘模型转化后就成了最小点覆盖，但是这题需要离散化，变成最小权点覆盖，用网络流求解即可。
CF1070I Privatization of Roads in Berland
2400
关键点：分配资源，点边转二分图
好题。不妨考虑一个点度数是 \(d_i\)，同色邻边数是 \(a_i\)，则我们要求 \(d_i - a_i \le k\)，也就是 \(a_i \ge d_i - k\)。
观察发现同色边最好是公共点，否则没有意义。
不妨考虑重新思考这个问题：假设有若干资源，每条边可以为两边的点之一提供一个资源，每个点有一个最少资源数，构造一种方案。
建立二分图，左边是点和需求，右边是边，跑一个最大流就可以求出来。不满流直接无解，否则构造方案即可。
标签：二分,右边,左边,Codeforces,flows,最小,2400,关键点 From： https://www.cnblogs.com/rlc202204/p/18315093