模型要点:

1.一般适用于二取一问题或者01规划。

2.利用最小割=最大流,转化为最大流求之。

建议阅读胡伯涛的论文 <<最小割模型在信息学竞赛的应用>>,有精彩有序的证明和各种模型。

相关题目：

1.太空飞行计划(网络流24题)

题目大意：

有一些实验和仪器,做每个实验有相应的报酬,但是需要买好相应的仪器(多个实验可以共用),仪器需要相应的钱.求最大利润。

题解：

经典的最大权闭合图模型。闭合图的概念是原图的一个点集,要求该点集的所有出边仍指向该点集合,最大权闭合图就是给每个点加一个权值,要求权值和最大。

转化一下,由最大变成最小。

S到正权值的点连边,容量为其权值,负权值的点到T连边，容量为其绝对值,然后原图中的边容量为inf,ans=所有正权和-最小割

2.方格取数(网络流24题)

题目大意:

矩阵中每个格子有一个数,要求取的格子不能相邻。要求取的数和最大。

题解：

这题让我学会了染色法,即把格子黑白染色,这样相邻的格子颜色一定不同,这样便转化为二分图的最大权独立集了。

最大权独立集的解法：

S到点的边和点到T的边容量为其权值,点与点之间的边容量为无穷大。这样对于任意一条从S到T得路径都对应相邻的两个点,割的作用就是二者取1。另外补充一个概念：像这样只有和ST相连的边的权值才不是无穷大的割叫做简单割。 这样求出的实际上是最小点权覆盖集,它和 最大权独立集是互补问题,具体证明可以用反证法。所以有最小点权覆盖集的权值+最大权独立集的权值=

总权值。

3.骑士共存(网络流24题)

题目大意:

在矩阵上放尽可能多的骑士,要求互不攻击。

题解：

同方格取数,染色+最大权独立集。

思考：

两个格子的颜色是否相同取决于 它们的曼哈顿距离的奇偶性。骑士的跳法和方格取数的规则都有两个格子颜色不同的性质。 那么如果改变骑士的跳法,每次只能沿着对角线跳一格。那么起点和中点的位置 颜色就相同了,就没法转化成二分图模型了。  我想到的做法仍然是染色,既然颜色不同的格子互相不影响,那么干脆把原矩阵拆成2个,黑白格子算.然后在分离出来的子矩阵里继续黑白染色执行之前的算法即可。

4.Friendship(poj 1815)

题目大意:

告诉你n个人之间的通话关系,然后要去掉尽可能少的人(不能去掉1号和n号),使得1号和n号不联通.人数相同要求字典序最小。

题解:

1.把人拆成2个点,连边容量为1,其他边容量为无穷大,求最小割就是答案。

2.要使字典序最小,可以用点贪心的思想,先求最小割,然后从2到n-1号依次枚举,把那个人暂时去掉,如果最小割减小了,那么永远把他去掉,否则把他加回去。

最小割 总结&&做题记录