题目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;

}

巴特西

[题解] [USACO05JAN]Muddy Fields G

题目大意

思路

C++代码

最新文章

热门文章