匈牙利算法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2063

就是一个匈牙利模板题，纯模板：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000 + 10;
int head[maxn], nextt[maxn * 2], to[maxn * 2], cnt = 2;
int n, k, m;
int vis[maxn], match[maxn];

void add(int u, int v) {
	to[cnt] = v; nextt[cnt] = head[u]; head[u] = cnt++;
}

bool Find(int x) {
	for (int i = head[x]; i != -1; i = nextt[i]) {
		int y = to[i];
		if (!vis[y]) {
			vis[y] = 1;
			if (!match[y] || Find(match[y])) {
				match[y] = x; return true;
			}
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	while (cin >> k && k) {
		cin >> n >> m;
		memset(match, 0, sizeof(match));
		memset(head,-1,sizeof(head));

		int u, v;
		for (int i = 1; i <= k; i++) {
			cin >> u >> v;
			add(u, v+n);
		}

		int ans = 0;
		for (int i = 1; i <= n; i++) {
			memset(vis,0,sizeof(vis));
			if (Find(i))ans++;
		}

		cout << ans << endl;
	}

	return 0;
}

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2236

基本就不会考裸的匈牙利算法，我们必须学会得去应用：

题意：

      这道题就是给你一个n阶方阵，从中选出n个数，这n个数的行和列都不相同（可以这样理解，一行只有一个数，一列也只有一个数），问这n个数的最大值与最小值的差值的最小值；

思路：

           如果是考虑搜索做法的话，很显然这是个个n！的复杂度，肯定实现不了。

           基于行和列不相同，把行作为一个集合，列作为一个集合，最后合理的选择其实就是一个二分图。

          之后我们枚举这个差值，用匈牙利算法判断是否合法。可是光知道差值还是不够啊，我们还得知道这些选出来数的范围啊。那我们就再枚举下界，这样就可以用匈牙利算法匹配了。然而这样的话算复杂度就是O（n^4）了。

这时候我们可以二分差值来降低复杂度。具体请参考代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100 + 10;
int head[maxn], nextt[maxn * 2], to[maxn * 2], cnt = 2;
int n, a[110][110];
int vis[maxn], match[maxn];

void add(int u, int v) {
	to[cnt] = v; nextt[cnt] = head[u]; head[u] = cnt++;
}

bool Find(int x,int l,int r) {
	for (int i = 1; i <= n;i++) {
		if (!vis[i]) {
			if (a[x][i]<l || a[x][i]>r)continue;       //如果这个数不在范围内，说明x不能和i匹配
			vis[i] = 1;
			if (!match[i] || Find(match[i],l,r)) {
				match[i] = x; return true;
			}
		}
	}
	return false;
}

bool check(int l, int r) {
	memset(match, 0, sizeof(match));
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		memset(vis,0,sizeof(vis));
		if (Find(i,l,r))ans++;
	}
	return ans == n;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t; cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];

		int l = 0, r = 100;  //差值的上下界
		while (r > l) {
			int mid = (l + r)/2;
			bool f = false;
			for (int i = 1; i + mid <= 100; i++) {  //枚举范围的下届
				if (check(i, i + mid)) {        //匈牙利算法检查是否合法
					f = true;
					break;
				}
			}
			if (f)r = mid;          //匹配成功，降低上界
			else l = mid + 1;         //匹配失败，降低下届
		}
		
		cout << r << endl;
	}

	return 0;
}