网络流建模合集
Just_int_mian · · 个人记录
自我整理ing...
1.限制类
- 这是一条只能单向通过的权值为
w 的双向边。
- 把
1 和2 划分到不同的集合有不同的收益,但如果1 和2 同时处于集合S ,额外获得a_1 收益,如果1 和2 同时处于集合T ,额外获得a_2 收益。 - 收益当然是保留下来的最大值。仔细观察这个结构,可以发现两个绿色虚点和
\infty 边的存在让一旦有一个点处于S 集合,a_2 则必须被划掉,反之亦然。这也是该建模的正确性证明。
哎呀呀,我不会网络流啊。
我也不会SPFA。