VJ193259 C Asa's Chess Problem

Concept 上下界网络流 顾名思义，比普通的网络流多出了下界。 考虑将下界的流量限制进行转化。将原来的边(e, v1->v2)拆边，拆出一条上界为 max-min 的边(e1)，和一条上界为 min 的边(e2, 虚拟存在)。 e2 需要满足满流方才有解，但满流的同时还需要保证流量守恒（入流==出流）。故而构造虚拟源点 SS 和虚拟汇点 TT . 对于点v, 若： 下限入流等于下限出流，则两者平衡，可以认为这两个流出流入的流量都不存在。 下限入流(flowin)大于下限出流(flowout)，则 SS 向 v 连一条容量为 flowin-flowout 的边，弥补不足流量。 下限入流(flowin)小于下限出流(flowout)，则 v 向 TT 连一条容量为 flowout-flowin 的边，弥补过剩流量。 当且仅当 SS 的所有边都满流时有解。跑一遍 SS 到 TT 的最大流，然后验证即可。 有源汇上下界可行