网络流建模合集

Just_int_mian · 2024-12-20 20:58:03 · 个人记录

自我整理ing...

1.限制类

• 这是一条只能单向通过的权值为 w 的双向边。

• 把 1 和 2 划分到不同的集合有不同的收益，但如果 1 和 2 同时处于集合 S，额外获得 a_1 收益，如果 1 和 2 同时处于集合 T，额外获得 a_2 收益。
• 收益当然是保留下来的最大值。仔细观察这个结构，可以发现两个绿色虚点和 \infty 边的存在让一旦有一个点处于 S 集合，a_2 则必须被划掉，反之亦然。这也是该建模的正确性证明。

哎呀呀，我不会网络流啊。

我也不会SPFA。