二分图匹配
二分图：把无向图 G = （V，E）分为两个集合 V1，V2，所有的边都在 V1 和 V2 之间，而 V1 或 V2 的内部没有边。V1 中的一个点与 V2 中的一个点关联，称为匹配。
染色法：一个图是否为二分图，一般用“染色法”进行判断。用两种颜色对所有顶点进行染色，要求一条边所连接的两个相邻顶点的颜色不相同。染色结束后，如果所有相邻顶点的颜色都不相同，它就是二分图。
结论：一个图是二分图，当且仅当它不含边的数量为奇数的圈。
二分图最大匹配问题
二分图最大匹配问题：无权图，求包含边数最多的匹配，即二分图的最大匹配。
匈牙利算法
时间复杂度:
匈牙利算法可以看成最大流的一个特殊实现。
由于二分图是一个很简单的图，并不需要做一个标准的最大流，可以进行简化。
- 从上面的图解中发现对 s 和 t 的操作是多余的，直接从 a、b、c 开始找增广路径就可以了。
- 残留网络上的增广路需要覆盖完整的路径，如果在二分图中进行{a、b、c}到{x、y、z}的局部操作，将之用一个数组match[]就有覆盖整个路径的效果。
// 络谷 板子题（https://www.luogu.com.cn/problem/P3386）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 501;
const int maxm = 5e4+1;
struct edge{
int to, next;
}e[maxm<<1]; int head[maxn], tot;
int match[maxn];
bool vis[maxn];
void addedge(int u, int v) {
e[++tot] = {v, head[u]}, head[u] = tot;
}
int dfs(int x) {
for(int i = head[x]; ~i; i = e[i].next) {
int j = e[i].to;
if (vis[j]) continue;
vis[j] = true;
if (!match[j] || dfs(match[j])) {
match[j] = x;
return 1;
}
}
return 0;
}
int main() {
int nx, ny, m; scanf("%d%d%d", &nx, &ny, &m);
memset(head, -1, sizeof head), tot = -1;
for(int i = 1; i <= m; ++ i) {
int u, v; scanf("%d%d", &u, &v);
addedge(u, v);
}
int maxmatch = 0;
for(int i = 1; i <= nx; ++ i) {
memset(vis, false, sizeof vis);
maxmatch += dfs(i);
}
printf("%d\n", maxmatch);
return 0;
}Hopcroft-Krap算法
时间复杂度：
预先找到多条路径最短的增广路，然后匈牙利算法就沿着bfs找的路径去找增广路。
bfs具体步骤：
- 把 V1 中所有没匹配的点加入队列
- 每次出来一个点 x，对于它连的 V2 中的每个点 y，如果 y 没访问过且没匹配过，找到增广路，否则把 y 的匹配点压入队列
// hdu 2063 （http://acm.hdu.edu.cn/showproblem.php?pid=2063）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 501;
const int inf = 0x3f3f3f3f;
vector<int> g[maxn];
int cx[maxn], cy[maxn];
int dx[maxn], dy[maxn];
int vis[maxn];
int bfs(int n) { // bfs搜索多条不想交最短增广路径
memset(dx, 0, sizeof(dx));
memset(dy, 0, sizeof(dy));
queue<int> q;
for(int i = 1; i <= n; ++ i) {
if (!cx[i]) q.push(i);
}
int dis = inf;
while(!q.empty()) {
int t = q.front(); q.pop();
if (dx[t] >= dis) continue;
for(auto i: g[t]) {
if (dy[i]) continue; // 多条路径不想交
dy[i] = dx[t] + 1;
if (!cy[i]) dis = dy[i]; // 最短路径已找到
else {
dx[cy[i]] = dy[i];
q.push(cy[i]);
}
}
}
return dis != inf;
}
int dfs(int x) { // 按照bfs搜索路径进行dfs
for(auto i: g[x]) {
if (vis[i] || dy[i] != dx[x] + 1) continue;
vis[i] = 1;
if (!cy[i] || dfs(cy[i])) {
cx[x] = i, cy[i] = x;
return 1;
}
}
return 0;
}
int HK(int n) { // HK算法
memset(cx, 0, sizeof(cx));
memset(cy, 0, sizeof(cy));
int res = 0;
while(bfs(n)) {
memset(vis, 0, sizeof(vis)); // 模拟dy[] 保证路径不相交
for(int i = 1; i <= n; ++ i) {
if (!cx[i] && dfs(i)) res ++;
}
}
return res;
}
int main() {
int n; while(scanf("%d", &n), n) {
int x, y; scanf("%d%d", &x, &y);
for(int i = 1; i <= x; ++ i) g[i].clear();
for(int i = 1; i <= n; ++ i) {
int u, v; scanf("%d%d", &u, &v);
g[u].push_back(v);
}
printf("%d\n", HK(x));
}
return 0;
}
Dinic 算法
用网络流来写二分图最大匹配。
// 络谷 板子题（https://www.luogu.com.cn/problem/P3386）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5010 << 1;
const int maxm = 5e4 + maxn;
struct edge{
int to, next, cap, flow;
}e[maxm<<2]; int head[maxn], tot;
int nx, ny, m, s, t, d[maxn], cur[maxn];
void addedge(int u, int v, int w) {
e[++tot] = {v, head[u], 1, 0}, head[u] = tot;
e[++tot] = {u, head[v], 0, 0}, head[v] = tot;
}
void init() { // 连接源点 和 汇点
memset(head, -1, sizeof head);
tot = -1;
s = nx + ny + 1;
for(int i = 1; i <= nx; ++ i) {
addedge(s, i, 1);
}
t = nx + ny + 2;
for(int i = 1; i <= ny; ++ i) {
addedge(i + nx, t, 1);
}
}
bool bfs() {
memset(d, 0x7f, sizeof d);
queue<int> q; q.push(t);
d[t] = 0;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; ~i; i = e[i].next) {
int j = e[i].to;
if (d[j] > d[x] + 1 && e[i^1].cap > e[i^1].flow) {
d[j] = d[x] + 1;
if (j == s) return true;
q.push(j);
}
}
}
return false;
}
int dfs(int x, int flow, int used = 0) {
if (x == t) return flow;
// for(int i = cur[x]; ~i && flow != used; i = e[ cur[x] = i ].next) { // 当前弧优化
for(int i = head[x]; ~i && flow != used; i = e[i].next) {
int j = e[i].to, f;
if (d[x] - 1 == d[j] && e[i].cap > e[i].flow) {
f = dfs(j, min(flow - used, e[i].cap - e[i].flow));
if (f) e[i].flow += f, e[i^1].flow -= f, used += f;
}
}
if (!used) d[x] = 0; // 剪枝优化
return used;
}
int main() {
scanf("%d%d%d", &nx, &ny, &m);
init();
for(int i = 1; i <= m; ++ i) {
int u, v; scanf("%d%d", &u, &v);
addedge(u, v + nx, 1);
}
int maxflow = 0;
while(bfs()) {
// memcpy(cur, head, sizeof head);
maxflow += dfs(s, INT_MAX);
}
printf("%d\n", maxflow);
return 0;
}
二分图求最大权匹配
KM 算法
时间复杂度：
KM算法：用于求二分图匹配的最佳匹配（最大权完美匹配）。
算法过程：
- 用邻接矩阵存图，给每个点加一个期望（cx[] 或 cy[]），当一对匹配的期望和等于其权值时该匹配才有可能匹配，我们需要最大权值和，所以先假设期望可以最大 cx[i] = max{与它有关的匹配权值}，cy[i] = 0。
- 尝试对第 i 个点进行匹配，若匹配成功，则进行下一个；若匹配失败，则降低左边已匹配点和该点的期望，提高右边已匹配点的期望，通过降低期望的方式尝试与独立点进行匹配，重复操作2。
注：初始化各点期望后，实线为可能匹配，虚线暂时不能匹配。（绿色为匹配成功，黄色为增广路，红色为匹配失败）
注： 若经过图四修改后 x2 仍然匹配失败，则重复图四修改即可。
注：代码中 km算法 是完备匹配下的最大期望，若初始化为0，则是最大权值和。
// hdu 2255 （http://acm.hdu.edu.cn/showproblem.php?pid=2255）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 301;
int graph[maxn][maxn];
int match[maxn], hx[maxn], hy[maxn], d[maxn], pre[maxn];
bool vis[maxn];
int km(int n) {
memset(match, 0, sizeof match);
for(int i = 1; i <= n; ++ i) { // 初始化期望权值
hx[i] = INT_MIN, hy[i] = 0;
for(int j = 1; j <= n; ++ j) {
hx[i] = max(graph[i][j], hx[i]);
}
}
for(int i = 1; i <= n; ++ i) { // 尝试匹配
memset(d, 0x7f, sizeof d);
memset(vis, false, sizeof vis);
int pos = 0, y;
match[pos] = i;
do { // 通过不段提高期望来满足匹配
int dis = INT_MAX, x = match[pos];
vis[pos] = true;
for(int j = 1; j <= n; ++ j) {
if (vis[j]) continue;
if (d[j] > hx[x] + hy[j] - graph[x][j]) {
d[j] = hx[x] + hy[j] - graph[x][j];
pre[j] = pos;
}
if (dis > d[j]) {
dis = d[j];
y = j;
}
}
for(int j = 0; j <= n; ++ j) {
if (vis[j]) hx[ match[j] ] -= dis, hy[j] += dis;
else d[j] -= dis;
}
pos = y;
} while(match[pos]);
for(int j = pos; j; j = pre[j]) {
match[j] = match[ pre[j] ];
}
}
int res = 0;
for(int i = 1; i <= n; ++ i) {
res += graph[ match[i] ][i];
}
return res;
}
int main() {
int n; while(~scanf("%d", &n)) {
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= n; ++ j) {
scanf("%d", &graph[i][j]);
}
}
printf("%d\n", km(n));
}
return 0;
}
京公网安备 11010502036488号