最小割構圖

最小割構圖

二分圖中，用最小割表示變量之間的關系。

下面用\(x\rightarrow y\)表示條件x滿足則條件y滿足。

同時令\(x_l\)表示\(x\)是一個左邊的點，\(x_r\)表示右邊的點。

直接連邊\(x_l\)到\(y_r\)，邊權為\(\infty\)。

連邊\(y_r\)到\(x_l\)，邊權為\(\infty\)

連邊\(x_r\)到\(y_r\)，邊權為\(\infty\)。

連邊\(x_l\)到\(y_l\)，邊權為\(\infty\)。

順便提一下，可以把\(\infty\)替換成任意值，表示讓這個限制失效的代價。