【图论】二分图匹配总结

二分图匹配总结

二分图匹配

1、二分图最大匹配。求两个集合内，每一个元素仅仅能用一次。两集合间存在一些匹配关系，求最大匹配多少对，利用匈牙利算法，对于每一个结点不断去找增广路去匹配

有几个重要性质:

1、最小点覆盖 = 最大匹配
2、最大独立集 = 总结点 - 最大匹配

模板：

bool dfs(int u) {
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (vis[v]) continue;
		vis[v] = 1;
		if (!left[v] || dfs(left[v])) {
			left[v] = u;
			return true;
		}
	}
	return false;
}

int hungary() {
	int ans = 0;
	memset(left, 0, sizeof(left));
	for (int i = 1; i <= G; i++) {
		memset(vis, 0, sizeof(vis));
		if (dfs(i)) ans++;
	}
	return ans;
}

假设要求最小点覆盖中，选中的点，就能够从每一个未匹配的点进去做增广路。然后未盖点就是答案：

bool dfs(int u) {
	S[u] = 1;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (T[v]) continue;
		T[v] = 1;
		if (!left[v] || dfs(left[v])) {
			left[v] = u;
			right[u] = v;
			return true;
		}
	}
	return false;
}

int hungary() {
	int sum = 0;
	memset(left, 0, sizeof(left));
	memset(right, 0, sizeof(right));
	for (int i = 1; i <= r; i++) {
		memset(S, 0, sizeof(S));
		memset(T, 0, sizeof(T));
		if (dfs(i)) sum++;
	}
	return sum;
}

void print() {
	memset(S, 0, sizeof(S));
	memset(T, 0, sizeof(T));
	for (int i = 1; i <= r; i++) {
		if (!right[i]) //从未匹配点进去dfs
			dfs(i);
	}
	/*for (int i = 1; i <= r; i++)
		if (!S[i]) //未盖点就是答案
	for (int i = 1; i <= c; i++)
		if (T[i]) //剩下未被覆盖的点
	*/
}

二分图匹配能够解决很多问题

最大匹配问题：最朴素的题目就是求两个集合最大能匹配几对。建图跑匈牙利算法就可以

最小点覆盖问题：常见的有行列模型，不能有同一行同一列出现的时候，往往就是把行列拆成两个集合，最二分图匹配

最大独立集：这类问题比較多。最小路径覆盖也是一类，假设问题中限制了入度出度为1，往往也是二分图匹配

POJ 1466 Girls and Boys 最小点覆盖
POJ 1719 Shooting Contest 最大匹配
POJ 1422 Air Raid 最小路径覆盖
POJ 2594 Treasure Exploration 最小路径覆盖变形
POJ 3216 Repairing Company 最小路径覆盖
POJ 3041 Asteroids 最小点覆盖（行列模型）
POJ 2771 Guardian of Decency 最大独立集
POJ 1325 Machine Schedule 最小点覆盖
POJ 1486 Sorting Slides 二分图的必须边（做法就是枚举删除边，看最大匹配变不变）
POJ 2536 Gopher II 简单二分图匹配
POJ 2239 Selecting Courses 最大匹配
POJ 1274 The Perfect Stall 最大匹配
POJ 2724 Purifying Machine 最大独立集合，注意怎样建模
POJ 3020 Antenna Placement 最大匹配
POJ 2446 Chessboard 最大匹配
POJ 2226 Muddy Fields 最小点覆盖（行列模型）
POJ 1548 Robots 最小路径覆盖
POJ 3692 Kindergarten 最大独立集
POJ 2060 Taxi Cab Scheme 最小路径覆盖

KM最大匹配

这类问题，是在二分图匹配的基础上，边有权值，还要计算出匹配后的最大权值是多少

假设是问最小权值，事实上仅仅要把边的权值变成负的。思路还是一样

KM最大匹配模板，复杂度（n^3)：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXNODE = 505;

typedef int Type;
const Type INF = 0x3f3f3f3f;

struct KM {
	int n, m;
	Type g[MAXNODE][MAXNODE];
	Type Lx[MAXNODE], Ly[MAXNODE], slack[MAXNODE];
	int left[MAXNODE], right[MAXNODE];
	bool S[MAXNODE], T[MAXNODE];

	void init(int n, int m) {
		this->n = n;
		this->m = m;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				g[i][j] = -INF;
	}

	void add_Edge(int u, int v, Type val) {
		g[u][v] = val;
	}

	bool dfs(int i) {
		S[i] = true;
		for (int j = 0; j < m; j++) {
			if (T[j]) continue;
			Type tmp = Lx[i] + Ly[j] - g[i][j];
			if (!tmp) {
				T[j] = true;
				if (left[j] == -1 || dfs(left[j])) {
					left[j] = i;
					right[i] = j;
					return true;
				}
			} else slack[j] = min(slack[j], tmp);
		}
		return false;
	}

	void update() {
		Type a = INF;
		for (int i = 0; i < m; i++)
			if (!T[i]) a = min(a, slack[i]);
		for (int i = 0; i < n; i++)
			if (S[i]) Lx[i] -= a;
		for (int i = 0; i < m; i++)
			if (T[i]) Ly[i] += a;
	}

	Type km() {
		memset(left, -1, sizeof(left));
		memset(right, -1, sizeof(right));
		memset(Ly, 0, sizeof(Ly));
		for (int i = 0; i < n; i++) {
			Lx[i] = -INF;
			for (int j = 0; j < m; j++)
				Lx[i] = max(Lx[i], g[i][j]);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) slack[j] = INF;
			while (1) {
				memset(S, false, sizeof(S));
				memset(T, false, sizeof(T));
				if (dfs(i)) break;
				else update();
			}
		}
		Type ans = 0;
		for (int i = 0; i < n; i++) {
			//if (right[i] == -1) return -1;
			//if (g[i][right[i]] == -INF) return -1;
			ans += g[i][right[i]];
		}
		return ans;
	}
} gao;

HDU 2255 奔小康赚大钱 模板题
HDU 1533 Going Home 最小匹配，边赋值成负就可以
HDU 1853 Cyclic Tour 一类经典题，每一个点限制了入度出度。能够转化为二分图匹配
HDU 3488 Tour 同上
HDU 3435 A new Graph Game 同上
HDU 2426 Interesting Housing Problem KM最大匹配
HDU 2853 Assignment KM最大匹配（这题的思路挺巧妙也挺有启示性的，假设一个权值要多一个优先级，就把这个值离散掉。然后多+1，这样优先级就变成最高的。却不影响结果）
HDU 3718 Similarity KM匹配，注意建模
HDU 3722 Card Game KM匹配
HDU 3395 Special Fish KM匹配
HDU 2282 Chocolate KM匹配，拆点
HDU 2813 One fihgt one KM匹配
HDU 2448 Mining Station on the Sea KM匹配+最短路
HDU 2236 无题II 二分+枚举+二分图匹配
HDU 3315 My Brute 同HDU2853
HDU 3523 Image copy detection KM匹配，读懂题意就非常明显了