一点废话

一直以来都没有太搞懂匹配，遇到别人眼里一眼出的匹配问题也经常看不懂，想想高中研究匹配的时候似乎就没吃透，导致现在还是有漏洞，这次详细研究一下，记录一点新的理解

最大匹配

匹配数量最多的情况

最优匹配/完美匹配

二分图中每个点都能匹配的情况。之前总是最大匹配最优匹配傻傻分不清

交替路

从一个非匹配点出发，依次经过非匹配边、匹配边、非匹配边……形成的路径叫做交替路。

增广路

经过另一个非匹配点的交替路。因此增广路中匹配边总是比非匹配边多1，取反后可以增加匹配数量。

深度优先/广度优先

深度优先：匹配冲突立刻找增广路，见的比较多。
广度优先：匹配冲突先看有没有其他可行匹配，都不行再用增广路。

KM算法

用来求带权二分图最大匹配问题，主要参考了这篇博客，理解之后发现复杂度相当暴力，看来不可避免需要继续学习其他高级算法。
例题：HDU2255

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;

#define clr(x) memset(x, 0, sizeof(x))

const int N = 309;
const int INF = 1e9;

int n;
int a[N][N];
int lx[N], ly[N], link[N], slack[N], vsx[N], vsy[N];

bool dfs(int x)
{
	vsx[x] = 1;
	for (int i = 1; i <= n; ++i)
	{
		if (vsy[i])
			continue;
		int temp = lx[x] + ly[i] - a[x][i];
		if (!temp)
		{
			vsy[i] = 1;
			if (!link[i] || dfs(link[i]))
			{
				link[i] = x;
				return true;
			}
		}
		else
			slack[i] = min(slack[i], temp);
	}
	return false;
}

int KM(int n)
{
	clr(lx);
	clr(ly);
	clr(link);
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			lx[i] = max(a[i][j], lx[i]);
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		memset(slack, 0x3f, sizeof(slack));
		// for (int j = 1; j <= n; ++j)
		// slack[j] = INF;
		for (;;)
		{
			clr(vsx);
			clr(vsy);
			if (dfs(i))
				break;
			int dlt = INF;
			for (int j = 1; j <= n; ++j)
			{
				if (!vsy[j])
					dlt = min(dlt, slack[j]);
			}
			for (int j = 1; j <= n; ++j)
			{
				if (vsx[j])
					lx[j] -= dlt;
				if (vsy[j])
					ly[j] += dlt;
			}
		}
	}
	int res = 0;
	for (int i = 1; i <= n; ++i)
	{
		res += lx[i] + ly[i];
	}
	return res;
}

int main()
{

	while (~scanf("%d", &n))
	{
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= n; ++j)
			{
				scanf("%d", &a[i][j]);
			}
		}
		printf("%d\n", KM(n));
	}
	return 0;
}