NOI2019序列非启发式做法

建立这道题的费用流模型:
如果都必须选(a_i,b_i),考虑拆边,(s o i)连接费用(a_i)流量(1)(i o t)连费用(b_i)流量(1)的边。
如果可以选择任意下标,事实上就是我们最多选出(k-l)对任意下标。
考虑用中转点,由于有流量限制所以拆边。
拆出(p,p')(i o p)连接流量(1)的边费用(0)(p o p')连接流量(k-l)费用(0)的边。
这道题的数据范围不允许直接运行费用流。
考虑模拟费用流,维护(p o p')边的流量(s)
设我们现在选择(a_x,b_y)
情况1:选择(a_x,b_x),在图中就是走了(s o x o t)增广路,(s)不变。
情况2:选择(a_x,b_y)(x,y)任意。
在图中就是走了(s o x o p o p' o y o t)的增广路,(s--)
只有(s>0)才能走。
情况3:走(s o x o p o y o t)的增广路。
就是把(a_x)(b_x)(必须被选)配对,(b_y)和原来(a_y)配对的点配对。
情况4:走(s o x o p' o y o t)的增广路。
就是把(b_x)(a_x)(必须被选)配对,把(a_y)和原来(a_x)配对的点配对。
情况5:走(s o x o p' o p o y o t)的增广路。
就是把(a_x)(b_x)(必须被选)配对,(a_y)(必须被选)和(b_y)配对,同时(s++)
不可能走多遍(p,p'),这样子会走环,一定是不优的。
维护(vi)数组表示每个点是否被选过。
维护(a_i+b_i,a_i,b_i)(a'_i)(这代表(b_i)被选择,但是(a_i)未被选择的点的set),(b'_i)(这代表(a_i)被选择,但是(b_i)未被选择的点的set)这5个set即可。

原文地址:https://www.cnblogs.com/ctmlpfs/p/14899397.html