虽然二分图模板已然是十分熟悉，但当初练习的时候也只是搜图论列表一个个的练习模板。
话不多说，分析一下这题的构图。
4 4
*.*.
.***
***.
..*.
给定的4*4的图。
要求我们构造木板。每个点的木板可以有横向和纵向两方选择。题中要求选择最少的木板使全部的点都被盖住。
于是乎，构造图就是构造横向铺的木板和纵向的木板，在图中的当前点选择木板的话，就是横向木板和纵向木板之间有边。
1.构造纵向木板
1.4.
.345
234.
..4.
2构造横向木板
1.2.
.333
444.
..5.
然后 用横向木板和纵向木板构造二分图
对横向木板和纵向木板执行匹配
直接使用匈牙利算法即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#define MAXN 51
using namespace std;char map[MAXN][MAXN];
int x[MAXN][MAXN];
int y[MAXN][MAXN];
bool ans[MAXN*30][MAXN*30];
bool visited[MAXN*30];
int match[MAXN*30];
int R,C;bool Match( int pre ,int size )
{int i;for( i=1;i<=size;i++ )if( ans[pre][i] && !visited[i] ){visited[i]=true;if( match[i]==-1 || Match( match[i],size ) ){match[i]=pre;return true;}}return false;
}int main()
{while( ~scanf("%d %d",&R,&C ) ){int i,j;for( i=1;i<=R;i++ )scanf( "%s",&map[i][0]+1 );int sign1=1,sign2=1;for( i=1;i<=R;i++ )for( j=1;j<=C;j++ ){if( map[i][j]=='*' ) x[i][j]=sign1;if( map[i][j]=='*' && map[i][j+1]!='*' )sign1++;}for( j=1;j<=C;j++ )for( i=1;i<=R;i++ ){if( map[i][j]=='*' ) y[i][j]=sign2;if( map[i][j]=='*' && map[i+1][j]!='*' )sign2++;}//printf( "%d %d\n",sign1,sign2 );for( i=1;i<=R;i++ )for( j=1;j<=C;j++ ){if( map[i][j]=='*' )ans[ x[i][j] ][ y[i][j] ]=true;}int res=0;memset( match,-1,sizeof(match) );for( i=1;i<=sign1;i++ ){memset( visited,false,sizeof(visited) );if( Match(i,sign2) )res++;}printf( "%d\n",res );}return 0;
}