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;}