Java教程

最小割构图

本文主要是介绍最小割构图，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最小割构图

二分图中，用最小割表示变量之间的关系。

下面用\(x\rightarrow y\)表示条件x满足则条件y满足。

同时令\(x_l\)表示\(x\)是一个左边的点，\(x_r\)表示右边的点。

1. \(x_l\rightarrow !y_r,y_r\rightarrow !x_l\)

直接连边\(x_l\)到\(y_r\)，边权为\(\infty\)。

2.\(x_l\or y_r=1\)

连边\(y_r\)到\(x_l\)，边权为\(\infty\)

3. \(x_r\rightarrow y_r\)

连边\(x_r\)到\(y_r\)，边权为\(\infty\)。

4. \(x_l\rightarrow y_l\)

连边\(x_l\)到\(y_l\)，边权为\(\infty\)。

顺便提一下，可以把\(\infty\)替换成任意值，表示让这个约束失效的代价。

这篇关于最小割构图的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航