【二分图】匈牙利算法

来源

简单易懂的详解 .

我愿称之为 $ntr$ 算法

核心代码

LL mp[MS][MS]; // 关系图 1 有 0 无 
LL vis[MS]; //  表示是否询问过
LL match[MS]; // 表示匹配关系

int find(LL x){
	for(int i=1;i<=m;i++){
		if(mp[x][i] && !vis[i]){ // 有关系且未被询问过 
			vis[i] = 1;
			if(!match[i] || find(match[i])){ 
				match[i] = x;
				return 1;
			}
		}
	}
	return 0;
} 

例题

题目POJ 2063 .

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 509
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

LL n,m,k; // 男生人数 ,女生人数 ,关系个数 
LL mp[MS][MS]; // 关系图 1 有 0 无 
LL vis[MS]; //  表示是否询问过
LL match[MS]; // 表示匹配关系 match[1] = 2 表示 1号男 与 2号女 牵手 

int find(LL x){ // x 表示任何一个女生 
	for(int i=1;i<=m;i++){
		if(mp[x][i] && !vis[i]){ // 有关系且未被询问过 
			vis[i] = 1;
			if(!match[i] || find(match[i])){ // 男生没被牵手 或者 被ntr 
				match[i] = x;
				return 1;
			}
		}
	}
	return 0;
} 

int main() {
	ios::sync_with_stdio(false);
	while(cin >> k){
		if(k == 0) return 0;
		memset(match,0,sizeof match);
		memset(mp,0,sizeof mp);
		cin >> n >> m; // 女 男 人数 
		LL u,v,ans=0;
		for(int i=1;i<=k;i++){
			cin >> u >> v;
			mp[u][v] = 1; // 表示 女u 愿意与 男v 牵手 
		}
		for(int i=1;i<=n;i++){
			memset(vis,0,sizeof vis);
			if(find(i)) ans++; // i号 女生牵手成功 
		} 
		cout << ans << endl; // 配对成功数量 
	}
	
	return 0; 
}