二分图最大匹配/二分图最大权匹配
当遇到匹配题或者「矩阵中有行列限制」类题，常常使用二分图算法。
二分图最大匹配/二分图最小点覆盖
所谓最大匹配，就是找到大小最大的边集 \(S\)，使得对于 \(\forall e \in S\)，所有 $ e' \ne e \in S $ ，满足 $ e'_u \ne e_u$ 且 $ e'_v \ne e_v$。（人话：选最大的不具有公共端点的边的集合。）
所谓最小点覆盖，就是找到大小最小的点集 \(T\)，使得 \(\forall e \in E\)，都有 \(e_u\in T\) 或 \(e_v \in T\)。（人话：选最少的点，满足每条边至少有一个端点被选。）
对于所有二分图，都有：最大匹配大小=最小点覆盖大小。证明不会qwq。
实现：匈牙利算法
思路
算法核心：找“增广路”
遍历所有左侧点，每次进行以下流程：
- 尝试去寻找一个右侧点来匹配；
- 若该右侧点还没有匹配的左侧点，则找到了，回溯。否则进入该右侧点的匹配左侧点，回到1。
由于每次的 \(\text{dfs}\) 找匹配点是 $ \mathcal{O}(n+m)$ 的，因此匈牙利算法的时间复杂度为 $ \mathcal{O}(n(n+m))$。
代码
洛谷P3386 【模板】二分图最大匹配
const int N = 505;
int n, m, tag;
vector<int> g[N];
int match[N], vis[N];
int ans;
bool dfs(int u)
{
vis[u] = tag;
for (auto &&v : g[u])
if (!match[v] || vis[match[v]] != tag && dfs(match[v]))
{
match[v] = u;
return true;
}
return false;
}
int main()
{
cin >> n >> x >> m;
int u, v;
for (int i = 1; i <= m; i++)
scanf("%d%d", &u, &v), g[u].push_back(v);
for (int i = 1; i <= n; i++)
{
++tag;
ans += dfs(i);
}
cout << ans << endl;
return 0;
}
[HNOI2013]消毒
题意
有一个 \(a\times b\times c\) 的立方体，其中有一些格子需要消毒。
你可以使用一种消毒剂，花费 \(\min( x,y,z )\) 代价，给一个 \(x \times y \times z\) 的立方体消毒。
求将整个立方体消毒干净的最小代价。
思路
Easy version
首先从简单的情况考虑，想想二维怎么做。
假设我们选择了一个长为 \(x\)，宽为 \(y\) 的矩形（\(x>y\)），那么无论 \(x\) 如何变化，代价不变。因此 \(x\) 取最大值一定最优。
问题便转化成了在一个矩形上刷一行或一列，覆盖所有点的最小刷的次数。
即「选择最少的行、列，包含所有要选的点」，一眼最小点覆盖。
对每个行、列建点。若该格子需要消毒，则链接行点、列点。
最后跑一遍匈牙利即可。时间复杂度 \(\mathcal{O}((a+b)\times[(a+b)+ab])\)。
Hard version
在立方体上，利用刚刚的结论，我们可以刷掉一些层。
然后我们可以把剩下的层拿出来，拍扁成一个二维矩形，就变成了 Easy version。
至于刷掉哪些层，暴力枚举即可。
注意要选用最短的棱长枚举。不妨设 \(a\leq b\leq c\)，因为 \(a\times b\times c \leq 5\times 10^3\)，所以可以用反证法证明 \(a<=17\)。
时间复杂度 \(\mathcal{O}(2^a\times (b+c)\times[(b+c)+bc])\)。（\(a\leq b\leq c\)）
瓶颈是 \(a=b=c=17\)，数量级约为 \(1.3 \times 10^9\)，但是卡不满匈牙利。可以通过。