【做题笔记】网络流24题（1）

网络流24题刷了10道了，在这里总结一下。

一些结论

• 最大流=最小割
• 二分图最少顶点覆盖=>最小割
• 最大独立点集=>最少覆盖

题目

飞行员配对问题

二分图最大匹配，建立超级源汇跑最大流

=>传送门

圆桌问题

多重匹配，建立超级源汇跑最大流

=>传送门

餐巾计划问题

最大收益问题，建模跑费用流

=>传送门

分配问题

最大/最小完美匹配，建立超级源汇对二分图跑费用流

=>传送门

运输问题

按照题意建模跑费用流即可

=>传送门

方格取数问题

最大流=最小割，对棋盘建二分图跑最大流，再用总数减

=>传送门

骑士共存问题

最大流=最小割，对棋盘建二分图跑最大流，再用总数减

=>传送门

试题库问题

二分图最大匹配，建立超级源汇跑最大流，输出方案直接扫边

=>传送门

太空飞行计划问题

最大流=最小割，输出方案玄学卡深度即可

=>传送门

最小路径覆盖问题

最大流=最小割，递归输出路径

=>传送门

版权属于：Noire02

本文链接：https://noire02.moe/archives/net1.html

北京第三区交通委提醒您：复制千万条，版权第一条。转载删出处，博主两行泪。