ChungZH 的小窝
·
网络流题集
💡
原文中文，约3000字，阅读约需8分钟。
📝
内容提要
本文介绍了图论中的经典问题，包括最大流、最小路径覆盖、最小割、方格取数问题、狼和羊的故事、小M的作物、太空飞行计划问题和order问题。对每个问题，文章提供了建图方法和解题思路。
🎯
关键要点
- 最大流问题的建图方法涉及拆分书的节点以避免重复选择。
- 最小路径覆盖问题的定理为最小路径覆盖数等于点数减去二分图最大匹配数。
- 最小割问题通过黑白染色法进行建图，计算不选的方格。
- 狼和羊的故事中，最小割即为狼和羊之间的边被割掉的情况。
- 小M的作物问题中，使用虚点表示贡献，答案为总收益减去最小割。
- 太空飞行计划问题涉及最大权值闭合图模型。
- order问题中，租用机器的边容量可以被割掉，表示选择工作后可替代购买机器的成本。
➡️
