前言
学了网络流不能只会板 练习开始！
先丢一些理论
二分图匹配
网络流建模初级练习！
一个匹配就是左右的一个点
定义一个超级汇点在左边 向左边的点连一条容量为 \(1\) 的边
中间是容量为 \(1\) 的边
定义一个超级汇点在右边 向右边的点连一条容量为 \(1\) 的边
然后 最大流 = 二分图最大匹配
为什么？容易发现 如果能流一个流量就是一个匹配
时间复杂度 \(O(\sqrt nm)\)
二分图最小点覆盖
这是什么？
要求：在二分图中选点 保证每条边至少有一个端点被选中
难证 过
结论 最小点覆盖 = 最大匹配
二分图最大独立集
要求：在二分图中选最多的点 满足一条边都不被匹配
结论 最大独立集 = \(n\) - 最小点覆盖
感性理解
把最小点覆盖以外的点都取了 然后不取最小点覆盖的点即可
DAG 的最小路径覆盖
要求：在一个 DAG 中 用最小的不相交路径覆盖整个图
这个要推
因为是不相交路径
因此 一条路径一定满足路径中每个点入度出度都为 \(1\)
特别的 起点入度为 \(0\) 终点出度为 \(0\)
可以把每个点拆成两个点 然后变成一个二分图 中间连边
容易发现 路径最少 转化为满足 终点最少
因此 转化为左边没被选的点最少
不就是最大匹配问题？
结论 ： **最小路径覆盖 = \(n\) - 最大匹配 **