http://poj.org/problem?id=2226 (题目链接)
题意
给出一个只包含‘．’和‘＊’的矩阵，用任意长度的宽为1的木板覆盖所有的‘＊’而不覆盖‘．’，木板必须跟矩形的长或宽平行。问最少需要多少块木板。
Solution
这道题的构图非常巧妙，堪称经典构图。对于每一个‘＊’，要么就是被横的木板覆盖，要么就是被竖的木板覆盖，而木板的长度一定都是取到最长（因为题目没有说木板不能重叠，所以木板尽可能长不会使答案变大）。
假设我们全部用横木板进行覆盖，那么可以很简单的统计出哪些地方用第几块木板覆盖；同样如果我们全部用竖的木板进行覆盖，也可以统计出哪些地方用第几块木板覆盖。所以我们最后要选择的木板就在这些木板中产生。
拿样例来举个例子：
横：1 0 2 0 竖：1 0 4 0
0 3 3 3 0 3 4 5
4 4 4 0 2 3 4 0
0 0 5 0 0 0 4 0
所以现在问题就转化成了如何选取最少的木板，使所有的‘＊’都被覆盖。这是不是很像二分图匹配中的最小点覆盖，可问题是我们怎么对它构图呢？
对于每一个‘＊’，都会有一个横木板和竖木板在这个位置相交。那么如果我们对于每一个‘＊’给在这里相交的横木板和竖木板的编号连一条边，是不是每一条边都表示一个‘＊’呢？答案是显然的。问题到这里也就迎刃而解了。最小点覆盖＝最大匹配数，所以我们只需要连完边后跑匈牙利就可以了。
代码
// poj2226
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
inline LL getint() {
int f,x=0;char ch=getchar();
while (ch<='0' || ch>'9') {if (ch=='-') f=-1;else f=1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
} const int maxn=1000;
struct edge {int to,next;}e[maxn*maxn];
int n,m,cnt,head[maxn],a[maxn][maxn],x[maxn][maxn],y[maxn][maxn],p[maxn],vis[maxn];
char s[maxn]; void insert(int u,int v) {
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
bool find(int x) {
for (int i=head[x];i;i=e[i].next) if (!vis[e[i].to]) {
vis[e[i].to]=1;
if (p[e[i].to]==0 || find(p[e[i].to])) {
p[e[i].to]=x;
return 1;
}
}
return 0;
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) {
scanf("%s",s);
for (int j=0;j<m;j++) {
if (s[j]=='*') a[i][j+1]=1;
else a[i][j+1]=0;
}
}
int xx=0,yy=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) if (a[i][j]>0) {
x[i][j]=++xx;
while (j<m && a[i][j+1]>0) {j++;x[i][j]=xx;}
}
for (int j=1;j<=m;j++)
for (int i=1;i<=n;i++) if (a[i][j]>0) {
y[i][j]=++yy;
while (i<n && a[i+1][j]>0) {i++;y[i][j]=yy;}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (a[i][j]>0) insert(x[i][j],y[i][j]);
int ans=0;
for (int i=1;i<=xx;i++) {
for (int j=1;j<=yy;j++) vis[j]=0;
if (find(i)) ans++;
}
printf("%d\n",ans);
return 0;
}