2226 Muddy Fields：木板填泥地，二分图最少定点覆盖-图解+分析

题目描述

思路分析

可以先看一道基础题，和这道题非常类似。在基础题中，我们将行/列分开作为二分图的点，如果某个坐标(x,y)上有个小行星，那么我们将x与y进行连接，也就意味着要么我们在横坐标位x的一行整一下，要么在纵坐标为y的一列整一下，如此这般，只要我们的所有边都至少有一个点连接，所有的小行星就都嗝屁了，于是问题转化为二分图最大匹配问题（最大匹配=最小顶点覆盖）

如果你理解上上面的意思，那么这道题其实就是一个进阶版，他们的不同点在于：

• 一行或一列不能只用一个木板填充，可能会要有要多个（因为我们不能整到草坪上）

怎么办呢？先按照上面的思路，单独对行和列进行统计

4 4   横    纵
*.*. 1020 1040 
.*** 0333 0345
***. 4440 2340
..*. 0050 0040

对横的而言，第一行显然需要两块模板，1，2，第二行只需要一块3.以此类推，显然我们可以使用一个贪心的策略，来求出横向的每一行需要的木块的序号。然后怎么办呢?对小行星问题，我们在每一个小行星（x，y）的位置，连接二分图中的x和y。那么这里其实也一样：
每遇到一个坑，我们就链接这个坑对应坐标的横，纵值

i-j的链接也就意味着要么用横着的第i块板，要么用竖着的第j块板才能覆盖掉这个坑，所有问题又转化成了求一个最小点集，覆盖所有的边=>二分图最大匹配。
我们将上图画完:

可以进行一个简单的目测，左1，左3，左4，右4这四块板子就可以覆盖所有边，不妨回到这里

4 4   横    纵
*.*. 1020 1040 
.*** 0333 0345
***. 4440 2340
..*. 0050 0040

这四块板正是我们要求的答案。

tips

• 求最大匹配个数的时候一定要清楚，参与匹配的不是横有多少行，竖有多少列，而是横着的需要的所有木板匹配竖着需要的所有木板，注意数组开的大小。

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<string.h>
#include<vector>
using namespace std;

#define MAX 55
#define MAXW 1000
#define inf 1e10
#define ll long long

char s[MAX][MAX];
ll r, c, w;//w:横着或者竖着需要使用木头数目
ll fit[MAXW][MAXW], row[MAX][MAX], col[MAX][MAX];
ll vis[MAXW], belong[MAXW];

bool match(ll k) {
	for (ll i = 1; i <= w; i++) {//这里最大是竖板需要的板子个数
		if (!vis[i] && fit[k][i]) {
			vis[i] = 1;
			if (belong[i] == -1 || match(belong[i])) {
				belong[i] = k;
				return true;
			}
		}
	}
	return false;
}

int main() {
	cin >> r >> c;
	for (ll i = 1; i <= r; i++)for (ll j = 1; j <= c; j++)cin >> s[i][j];
	ll cnt1 = 0, cnt2 = 0;
	//横着的板子
	for (ll i = 1; i <= r; i++)
		for (ll j = 1; j <= c; j++) {
			if (s[i][j] == '*') cnt1++;
			while (s[i][j] == '*') row[i][j] = cnt1, j++;
		}
	//竖着的板子
	for (ll i = 1; i <= c; i++) 
		for (ll j = 1; j <= r; j++) {
			if (s[j][i] == '*') cnt2++;
			while (s[j][i] == '*')col[j][i] = cnt2, j++;
		}
	w = cnt2;
	memset(fit, 0, sizeof(fit));
	for (ll i = 1; i <= r; i++)
		for (ll j = 1; j <= c; j++)
			if (s[i][j] == '*') {
				ll a = row[i][j], b = col[i][j];
				fit[a][b] = 1;
			}
	ll res = 0;
	memset(belong, -1, sizeof(belong));
	for (ll i = 1; i <= cnt1; i++) {//注意这里不是小于等于c，而是横板需要的板子的个数
		memset(vis, 0, sizeof(vis));
		if (match(i))res++;
	}
	cout << res << endl;
}