题解：P3386 【模板】二分图最大匹配

· · 题解

网络流二分图最大匹配

前言

这篇题解使用了 Dinic 算法解决了二分图最大匹配问题，但是和其他题解不同的是，我们使用了神秘的 vector。

本片题解会浅略讲解 vector 如何使用在网络流上，以及网络流如何解决二分图最大匹配问题。

在阅读本题解之前，你需要了解网络最大流。

vector 版网络流

vector 的难点是，其相对于链式前向星难以找到反边，所以我们应该为其找到一个 id 进行标记，用什么来记录这个 id 呢？答案是——数组大小！

我们约定 vector 数组 vector<Node> v[MN]。

可以发现，对于两个点 a、b，我们在从 a 连向 b 的时候存下 b 的数组大小 id，再从 b 连向 a，则 b 连向 a 这条边的下标就是 id，即 v[b][v[a].id] 就是 b 到 a 的边。

所以，我们可以写出 vector 加边的代码：

void add(int a,int b,int k){
    int sza=v[a].size(),szb=v[b].size();
    v[a].push_back({b,k,szb});
    v[b].push_back({a,0,sza});
}

同时，我们也知道了，vector 的结构体中需要存储连向的边、流量、id 三个内容。

网络流解决二分图最大匹配

我们设超级原点 s 和 超级汇点 t。

将所有左部点和 s 连接，将所有右部点和 t 连接，流量均应为 1，然后再按照题目给出的关系连接左右部点，在本题中流量也应为 1。

需要注意，右部点应该加上一定偏移来保证其编号不与左部点重合，例如在本题中，左部点共有 n 个，则右部点 b 的编号应该设置为 b+n 或更大。

最后从 s 跑网络流，答案即为所求。

为什么这样建边是正确的

因为在网络流中有反边的存在，所以我们只需要从左部点连向右部点，它就会自然地进行类似匈牙利算法的不断向下 DFS 的操作。

而连接超级原点和超级汇点是为了防止有遗漏，匈牙利算法就是因为无法解决遗漏问题而不得不多次进行 DFS。

代码

请见洛谷剪切板。

如不能访问上面连接，也可以访问洛谷保存站。

更新