[題解] [USACO05JAN]Muddy Fields G

• 2020 年 12 月 2 日
• 筆記
• 二分圖

• 題目TP門

題目大意

在一個 \(R×C\) 的矩陣中，每個點有兩個狀態：草地和泥地。你需要在泥地里鋪 \(1×k\) 木塊， \(k\) 為任意整數，求最少要多少木塊。

思路

兩個橫向木塊不會互相干擾，兩個豎向木塊不會互相干擾，且一個點的覆蓋方法只有橫向木塊覆蓋與豎向木塊兩種覆蓋方法，不難想到二分圖的最小點覆蓋。

設每個點 \(i\) 的豎向木板的編號為 \(belong1[i]\) ，橫向木板的編號為 \(belong2[i]\) ，則這個點可能會被 \(belong1[i]\) 與 \(belong2[i]\) 任意一個所覆蓋，所以將 \(belong1[i]\) 與 \(belong2[i]\) 連接一條邊。

最後在求出最小點覆蓋，就是最少需要木板的個數。

C++程式碼

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
void Quick_Read(int &N) {
	N = 0;
	int op = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-')
			op = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		N = (N << 1) + (N << 3) + (c ^ 48);
		c = getchar();
	}
	N *= op;
}
const int MAXN = 5e3 + 5;
const int MAXM = 55;
vector<int> v[MAXN];
int belong1[MAXM][MAXM], belong2[MAXM][MAXM];
char Mp[MAXM][MAXM];
int twin[MAXN];
bool vis[MAXN];
int r, c, n, m;
bool Hungary(int now) {//匈牙利演算法
	int SIZ = v[now].size();
	for(int i = 0; i < SIZ; i++) {
		int next = v[now][i];
		if(!vis[next]) {
			vis[next] = true;
			if(!twin[next] || Hungary(twin[next])) {
				twin[next] = now;
				return true;
			}
		}
	}
	return false;
}
int Match() {//匹配
	int res = 0;
	for(int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		if(Hungary(i))
			res++;
	}
	return res;//二分圖中最小點覆蓋就等於最大匹配
}
void Build() {
	n = 1;
	for(int i = 1; i <= r; i++) {//求出橫向木板
		bool last = false;
		for(int j = 1; j <= c; j++) {
			if(Mp[i][j] == '*') {
				belong1[i][j] = n;
				last = true;
			}
			else {
				if(last)
					n++;
				last = false;
			}
		}
		if(last)
			n++;
	}
	m = n + 1;
	n--;
	for(int j = 1; j <= c; j++) {//求出豎向模板
		bool last = false;
		for(int i = 1; i <= r; i++) {
			if(Mp[i][j] == '*') {
				belong2[i][j] = m;
				last = true;
			}
			else {
				if(last)
					m++;
				last = false;
			}
		}
		if(last)
			m++;
	}
	for(int i = 1; i <= r; i++)
		for(int j = 1; j <= c; j++)
			if(Mp[i][j] == '*')
				v[belong1[i][j]].push_back(belong2[i][j]);//建圖
}
void Read() {
	Quick_Read(r);
	Quick_Read(c);
	for(int i = 1; i <= r; i++)
		scanf("%s", Mp[i] + 1);
}
int main() {
	Read();
	Build();
	printf("%d", Match());
	return 0;
}