ZOJ 1654 二分匹配基础题

题意： 给你一副图，有草地(*)，空地(o)和墙(#)，空地上可以放机器人，机器人向上下左右4个方向开枪(枪不能穿墙)，问你在所有机器人都不相互攻击的情况下能放的最多的机器人数。

思路：这是一类经典题的衍化，如果没有墙，我们会将行和列看成两列点阵，然后就可以用二分匹配解。

现在有墙怎么办呢，把某一行或列(有墙的拆分成多个区域，可以看成多个行或列)，拆好以后更没有墙的做法一样了。

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int maxn = 1505;

vector <int> edge[maxn]; //记录以左排点为起点的单向边

int pre[maxn]; //右点阵的大小

bool vis[maxn]; //右点阵的大小

int n, m;

bool dfs(int u) {

	int i, v;

	for(i = 0; i < (int)edge[u].size(); i++) {

		v = edge[u][i];

		if(vis[v])

			continue;

		vis[v] = 1;

		if(pre[v] == -1 || dfs(pre[v])) {

			pre[v] = u;

			return 1;

		}

	}

	return 0;

}

char mp[51][51];

int num[51][51];

int nx, ny, x[maxn][maxn], y[maxn][maxn];

int main() {

	int i, j, cas, ca = 1;

	scanf("%d", &cas);

	while(cas--) {

		scanf("%d%d", &n, &m);

		for(i = 0; i < n; i++)

			scanf("%s", mp[i]);

		memset(x, -1, sizeof(x));

		nx = 0;

		for(i = 0; i < n; i++) {

			for(j = 0; j < m; j++)

				if(mp[i][j] == 'o') x[i][j]= nx;

				else if(mp[i][j] == '#') nx++;

			nx++;

		}

		memset(y, -1, sizeof(y));

		ny = 0;

		for(j = 0; j < m; j++) {

			for(i = 0; i < n; i++)

				if(mp[i][j] == 'o') y[i][j] = ny;

				else if(mp[i][j] == '#') ny++;

			ny++;

		}

		for(i = 0; i < nx; i++) edge[i].clear();

		for(i = 0; i < n; i++)

			for(j = 0; j < m; j++)

				if(mp[i][j] == 'o')

					edge[x[i][j]].push_back(y[i][j]);

		memset(pre, -1, sizeof(int)*ny);

		//建边

		int cnt = 0;

		for(i = 0; i < nx; i++) {

			memset(vis, 0, sizeof(int)*ny);

			if(dfs(i)) cnt++;

		}

		printf("Case :%d\n%d\n", ca++, cnt);

	}

	return 0;

}

巴特西

ZOJ 1654 二分匹配基础题

最新文章

热门文章