传送门：Muddy Fields
题意：一个由r行c列方格组成的田地，里面有若干个方格充满泥泞，其余方格都是草。要用长度不限，宽度为1的长木板来覆盖这些泥方格，但不能覆盖草地。最少要用多少个长木板。
分析：行列模型最小点覆盖，给连续行和列重新标号，然后每个字符*代表一条边，题目转换成用最少点覆盖所有的边（*）。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 100000000 #define inf 0x3f3f3f3f #define eps 1e-6 #define N 1010 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define PII pair<int,int> using namespace std; int match[N],vis[N],n,m; int vn,vm,r[N][N],c[N][N]; int g[N][N]; char s[N][N]; int dfs(int u) { for(int i=1; i<=vm; i++) { if(g[u][i]&&!vis[i]) { vis[i]=1; if(match[i]==-1||dfs(match[i])) { match[i]=u; return 1; } } } return 0; } int hungary() { FILL(match,-1); int ans=0; for(int i=1; i<=vn; i++) { FILL(vis,0); if(dfs(i))ans++; } return ans; } void build() { vn=vm=0;FILL(g,0); for(int i=1; i<=n; i++) { int first=1; for(int j=1; j<=m; j++) { if(s[i][j]=='*') { if(first)vn++; first=0; r[i][j]=vn; } else first=1; } } for(int i=1;i<=m;i++) { int first=1; for(int j=1; j<=n; j++) { if(s[j][i]=='*') { if(first)vm++; first=0; c[j][i]=vm; } else first=1; } } for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(s[i][j]=='*') { g[r[i][j]][c[i][j]]=1; } } int main() { while(scanf("%d%d",&n,&m)>0) { for(int i=1; i<=n; i++) scanf("%s",s[i]+1); build(); int res=hungary(); printf("%d ",res); } }