关于一类最小割模型的问题求助
这是第三帖了...
这个问题，大概连边的方法就是：(原谅我画的很烂)
其中 X 割掉连 S 的边代表 X 在 A 完成，割掉连 T 代表在 B 完成。
a/X\b
S |e T
c\Y/d
然后需要给图中 5 条边（设为 ）分别赋上非负的权值，最后图的最小割即为答案。
\begin{aligned} a + c = w1 \cdots(1)\\ b + d = w2 \cdots(2)\\ a + e + d = w3\cdots(3)\\ c + e + b = w4\cdots(4) \end{aligned} \right.然后 均可以直接加到正，但是 不能保证为正。
书上给的解决方法是改变连边的意义（X 割掉连 S 的边代表 X 在 B 完成，割掉连 T 代表在 A 完成。Y 连边的意义不变）：
则
\begin{aligned} a + c = w4 \cdots(1)\\ b + d = w3 \cdots(2)\\ a + e + d = w2\cdots(3)\\ c + e + b = w1\cdots(4) \end{aligned} \right.这样连边后的 ，就是正的了。
但是有个条件就是所有 的二元组， 这样连边后是二分图（否则会有 x 的意义既要改变又不改变的矛盾）。
书上只提了一句验证预设图是二分图就可以建模。
就想问一下预设图不是二分图这个问题怎么做。。
加载中...