题目：Muddy Fields
题意：
有一块矩形的农场，其中有一些地是草，有一些地是泥。现要将所有泥地上都铺上木板，且木板不能覆盖草。木板为矩形，且宽始终为1，木板可相互重合。
思路：
把每块木板看做点，两块木板的重合的点看做边（由于每个泥地都可以看做是两块木板的交点，所以可以知道图上的每条边和泥地一一对应）。
因为木板只有横和竖两种状态，所以可以人为的把点根据横竖分为两块。又由于横着的两块木板不想交，竖着的木板也互不相交，所以这两块点每块之间没有连边。所以可以知道，这张图是一个二分图。
然后对于这个二分图，我们要求用最少的覆盖到所有的边，即最小点覆盖，也就是求二分图的最大匹配。
对于二分图的匈牙利算法，我基本上忘光了，照着原来的模板打了一遍……
要注意建图只用建单向边就好。
代码：
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;#define maxn 50*50*2
#define readc(x) while((~scanf("%c",&x))&&x!='.'&x!='*')
#define read(x) scanf("%d",&x)
#define write(x) printf("%d",x)int n,m;
char mp[maxn+5][maxn+5];vector<int> g[maxn+5];
int id1[maxn+5][maxn+5],id2[maxn+5][maxn+5];
int cnt1,cnt2;int use[maxn+5],match[maxn+5];bool dfs(int x,int fa) {for(int i=0; i<g[x].size(); i++) {int y=g[x][i];if(use[y]||y==fa) continue;use[y]=true;if(!match[y]||dfs(match[y],x)) {match[y]=x;return true;}}return false;
}void readin() {read(n);read(m);for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)readc(mp[i][j]);for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)if(mp[i][j]=='*')if(mp[i-1][j]=='*') id1[i][j]=id1[i-1][j];else id1[i][j]=++cnt1;for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)if(mp[i][j]=='*')if(mp[i][j-1]=='*') id2[i][j]=id2[i][j-1];else id2[i][j]=(++cnt2)+cnt1;
}void makeg() {for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)if(mp[i][j]=='*') {g[id1[i][j]].push_back(id2[i][j]);}
}int slv() {int x=0;for(int i=1; i<=cnt1; i++) {memset(use,0,sizeof(use));x+=dfs(i,0);}return x;
}int main() {readin();makeg();write(slv());return 0;
}