文章

25

粉丝

0

获赞

0

访问

68536

头像
二分图的最大匹配-棋盘覆盖
经验总结
发布于2020年4月16日 23:44
阅读数 2688

二分图的最大匹配:匈牙利算法

int n1, n2;
int h[N], next_pos[N], e[N], idx;
int match[N];
bool st[N];
bool find(int x){
	for (int i = h[x]; i; i = next_pos[i]){
		int j = e[i];
		if (!st[j]){
			st[j] = true;
			if (!match[j] || find(match[j])){
				match[j] = x;
				return true;
			}
		}
	}
	return false;
}
int ans = 0;
for (int i = 1; i <= n1; i++){
	memset(st, false, sizeof st);
	if (find(i)){ ans++; }
}

(1)将集合视为点集,求点集的二分图最大匹配(只保存单向)

#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int n, m;
int g[N][N];//存放棋盘的删除点
bool st[N][N];
typedef pair<int, int>PII;
PII ret[N][N];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
bool find(PII x){//判断点x作为未被匹配的点出发是否存在增广路径
	for (int i = 0; i < 4; i++){
		int a = x.first + dx[i]; int b = x.second + dy[i];
		if (a <= 0 || a>n || b <= 0 || b > n || g[a][b] || st[a][b]){
			continue;
		}
		st[a][b] = true;
		if (ret[a][b].first == 0 || find(ret[a][b])){
			ret[a][b] = x;
			return true;
		}
	}
	return false;
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		g[x][y] = 1;
	}
	int ans = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (g[i][j] || (i + j) % 2 == 0){ continue; }
			memset(st, false, sizeof(st));
			if (find({ i, j })){
				ans++;
			}
		}
	}
	cout << ans << endl;


	return 0;
}

(2)存两条边

#include<iostream>
using namespace std;
const int N = 1000000;
int vis[20000];
struct node{
	int to, next, from;
}e[N];
int h[N], match[20000], idx;
int g[210][210];
void add(int a, int b){
	e[++idx].to = b;
	e[idx].from = a;
	e[idx].next = h[a];
	h[a] = idx;
}
int n, m;
int getHash(int i, int j){
	return (i - 1)*n + j;
}

bool find(int x){
	for (int i = h[x]; i; i =e[i].next){
		int now = e[i].to;
		if (vis[now]){ continue; }
		vis[now] = 1;
		if (!match[now] || find(match[now])){
			match[now] = x;
			match[x] = now;
			return true;
		}
	}
	return false;
}

int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		g[x][y] = 1;
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (g[i][j]){ continue; }
			int now = getHash(i, j);
			if (!g[i - 1][j] && i - 1 > 0){
				add(now, getHash(i - 1, j));
			}
			if (!g[i + 1][j] && i + 1 <= n){
				add(now, getHash(i + 1, j));
			}
			if (!g[i][j - 1] && j - 1 > 0){
				add(now, getHash(i, j - 1));
			}
			if (!g[i][j + 1] && j + 1 <= n){
				add(now, getHash(i, j + 1));
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n*n; i++){
		if (!match[i]){
			memset(vis, 0, sizeof vis); 
			if (find(i)){
				ans++;
			}
		}
	}
	cout << ans << endl;
	
	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发