非静态网络流总结

二分

求最大赢的人获胜次数最小
二分最小次数(val)
对于每个比赛新建一个节点(x)(Sxrightarrow{1}x),对于两个人(a、b)(xxrightarrow{1}a,xxrightarrow{1}b)
每个人向汇点(T)连容量为(val)的边,如果最大流=比赛个数则说明该次数可行

二分图(U)为武器,(V)为机器人,(Uxrightarrow{inf}V,Sxrightarrow{x}U,Vxrightarrow{x}T)
(x)取决于每个武器及时间,流量为(timecdot B_i),由于时间有单调性二分时间
精度到(10^{-3}),则二分到(10^{-4}),值都乘以(10^4),二分到整数即可

原文地址:https://www.cnblogs.com/y2823774827y/p/10921233.html