72-网络流问题解题秘籍

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

遇到一个实际问题，首先要分析：

（1）是否可以用网络流解决？

如果可以使用网络，则构建网络图，如果需要添加源点和汇点则添加之，并确定每条边的容量。

（2）是否可以直接用最大流解决？

如果可以，求解最大流就可以了，例如7.5～7.7节中的问题。

（3）问题的解是否是与最小割容量相关的表达式？

问题的解不能直接用最大流解决，需要分析问题的解，是不是最小割容量，还是与最小割容量相关的表达式。例如7.8节和7.9节中的问题，都是所有盈利减去最小割容量。最小割容量等于最大流值，所以可以通过求解最大流间接得到。

（4）是否可以用最小费用最大流解决？

有的问题可以转化为最小费用最大流问题，例如7.10节中的旅游路线问题。

（5）问题的解是什么？

在7.5～7.7节中，得到最大流后，x_i结点的邻接点y_i就是我们要的答案。

在7.8节中，问题的解就是最小割的S集合。S集合求解方式：在最大流对应的混合网络上，从源点出发，沿着容量>流量的边深度优先遍历。遍历到的结点就是S集合，没遍历到的结点就是T集合。

在7.9节中，问题的解是最小割中的S集合中的黑色方格和T集合中的白色方格。所以深度优先遍历得到S集合和T集合后，要输出S集合中的黑色方格和T集合中的白色方格。

在7.10节中，旅游路线问题的解是深度优先遍历结果，但是边的容量和流量有约束的深度遍历。