仔细思考了一下，发现自己还有许多弱项，网络流也是其中之一，而且只会写板子，需要补一补。
还有10天就GDOI了，要抓紧啊……
把每个人拆成两个点放在中间，左边房子右边菜，跑最大流即可。
黑白染色之后发现只能黑和白匹配，于是就是个二分图了，搞出最大匹配即可。
套路：黑白染色之后有可能会成为二分图。
把行和列作为点，格子作为边，如果可以放就把对应的行列连起来，然后跑最大匹配。
这样的匹配显然满足所有车都不同行不同列。
套路：行列作为点，格子作为边。
注意到一个性质：无论怎么换，同行的黑点仍然同行，同列的黑点仍然同列。
所以每行/列最多有一个黑点在对角线上。
那么和上一题一样的建图方法就可以做了。
显然在\(D(i,T_i)\)确定的情况下能与\(i\)匹配的\(T_i\)是常数级别的。
那么连一下二分图就可以得到一组解了。
用匈牙利算法，从后往前做，就可以字典序最小了。
考虑最终答案就是AB不同状态个数的和，也就是要用最少的状态，使得每个任务都被覆盖。
把A状态放左边，B状态放右边，每个任务视为一条边，那就是求这个二分图的最小点覆盖。
定理：二分图最小点覆盖包含的点数 == 二分图最大匹配包含的边数。
于是跑一个最大匹配就做完了。
套路：对于二者至少选其一的限制，将其视为边，做最小点覆盖。
一个显然的贪心：对于每一个木板，肯定会一直变长直到顶到边界或干净格子。
所以每个泥泞格子至少会被横着或竖着的两种木板之一覆盖。
用上一题的定理和套路就做完了。
按套路黑白染色一下，发现限制只会在黑白点之间，于是就变成了求二分图的最大独立集。
定理：设\(G\)是有\(n\)个节点的二分图，\(G\)的最大独立集大小 == \(n-\)最小点覆盖数 == \(n-\)最大匹配数。
那么就做完了。
首先发现朋友圈就是一个团。
然后发现A国是一个二分图，B国是两个团之间连了一些边。
定理：无向图 \(G\) 的最大团 == 补图 \(G'\) 的最大独立集。
发现A国最多选两个人，B国取个补图就变成了二分图。
那么可以枚举A国的人，把B国和他们是朋友的人提出来搞个补图，然后求补图（一个二分图）的最大独立集即可。
显而易见的思路是枚举每组喜欢关系，然后匈牙利算法判一下是否合法，不过貌似会T。
考虑优化判合法的过程。对于给定的方案\(x_i\rightarrow y_i\)，连一条\(y_i\rightarrow x_i\)的边，然后再把喜欢关系的边\(x_i\rightarrow y_i\)连上。
那么\(x_i\rightarrow y_j\)合法当且仅当\(x_i,y_j\)在同一强连通分量里，考虑匈牙利算法的实现过程，这显然正确。
那么就做完了，复杂度\(O(n+m)\)。
定理：有向无环图的最小路径点覆盖包含的路径条数 == \(n-\)其拆点二分图的最大匹配数
于是做完了。
首先求出每个点能到达哪些点（说得高端一点就是进行传递闭包）。
然后往能到的点都连上边，就变成最小路径点覆盖了。
把每一个石柱拆成入点出点，之间连上该石柱的高度的权值的边。
源点连蜥蜴位置，能跳出去的位置连汇点，位置之间互相连。
跑最大流即可。
套路：点有权值时拆点连边，转化为边的权值。
定理：最大流=最小割。
首先枚举不连通的两点。
拆点，把每一个点拆成入点和出点，之间连权值为1的边。割开这条边就等价于删点。
然后跑最小割即可。
黑白染色，发现只有黑白点之间会互相影响。
相邻的黑白点连权值\(\infty\)的边表示不能割开，\(S\)往黑点连权值为格子权值的边，白点往\(T\)连权值为格子权值的边。
用总权值减去最小割就是答案了。
这个图的意义：割开边表示不选，最后选了与\(S\)相连的黑点、与\(T\)相连的白点。
套路：最小割常用于表示分开两种不同状态。
原文：https://www.cnblogs.com/p-b-p-b/p/10741953.html