没想出要在简述这写什么emmm
问题描述:
n个点m点边,
每条边的流量有上下界,
存不存在可行方案使
所有点满足流量平衡,
所有边满足流量限制?
连边:
怎么连:
u->v流量上下限[lower,upper]
对于每条边u->v, 在 du[u]-=lower, du[v]+=lower
遍历所有边后, du[i]<0 的 i 和源点连一条流量为 -du[i] 的边
du[i]>0 的 i 和汇点连一条流量为 du[i] 的边
每条边u->v, u和v连一条流量为 upper-lower 的边
为什么:
首先要达到每条边的流量下限
然后[lower,upper]是个可选择的流量区间
每个点和它相连边的流量下限都要满足
把流入的流量下限减流出的流量下限
会发现这个值不一定等于0
但是会有一部分流入和流出的下限抵消了,也就是有一部分流量下限满足了
而没有抵消(也就是不等于0)的那部分,du[i]就由源点或者汇点抵消
当与源点或者汇点连的边跑满,就全部抵消了(剩余没抵消的流量下限也满足了),也就是存在可行方案
否则反之
跑完最大流后,在某条边跑过去的流量,就是一个选择的值
这个值加上流量下限就是满足这条边的可行流量(怎么搞出多个方案,目前不会)
20-08-02 upd:
为什么和源(汇)点流入(出)的流量可以流向可选择的那部分流量?
因为这两种流量都是每个点,出入流量得来的(被自己突然想出的脑残卡壳emm)
代码:
1 |
|
ps:在想为什么这么连边失眠一个多小时,所以这边建议不要睡前思考问题((/- -)/┻━┻