给你一个二分图 要求你求出对于 k=[0~Mindegree] 每个点的度数至少为 k 所需要的最少边数 并输出方案
如果是单个询问的话 直接跑一个下界网络流即可 但是有多个询问 重建图强行跑不行
反过来考虑, 变成至多能删除多少边则建边 [s,i,degree[i]-Mindegree] [i,T,degree[i]-Mindegree] [u,v,1]
这样跑出来的流 二分图中没有流量的边代表是要选的 有流量的是要删的 同时保证了每个点的度数不小于 Mindegree
则接下来每次对与 S,T 相连的边容量 ++ 得到 k=[0~Mindegree-1] 的答案
来源: http://www.bubuko.com/infodetail-3016186.html