上下界网络流

wl2009_pretty_girl · 2024-04-06 15:35:37 · 个人记录

CF1416F

将每个元素看成一个点，每个点不会走出矩阵，只有一条出边且可以走无限步，所以建好的图应为内向树森林。

A的每个元素均为正整数。 这是一个很重要的性质。基于这个条件，我们可以发现若u周围的点v均不满足s_{v} \leq s_{u}，则无法构造矩阵A和B。否则，一定存在一种构造方案。若u周围有一个点v满足s_{v}<s_{u}，则u可以向v连边，a_{u}=s_{u}-s_{v}，否则，u只能向周围权值相等的v连边，即u一定在环中。

发现环一定是偶环，可以将其拆成若干个二元环以减小构造难度。注意：二元环之间不能相交，这也是可以将矩阵黑白染色进行二分图匹配的原因。建立超级源点S和T，将S和黑点连边，T和白点连边。若一个点不一定在环中，则S(T)与其连边的下界为0，上界为1，否则上下界均为1。黑点和与其相邻且权值相等的白点连边，下界为0，上界为1。最后找到一组可行流即可。

找到一组可行流后若黑点和白点之间的边流满了，则表示这两个点构成了一个二元环，否则表示没有。