poj 2226 二分图匹配

这个题目容易想到dp，dfs，dp状态太多，会mle加tle，dfs会tle。

那么就只能往图论上面想了，注意到一个事实，任何一个格子只能被两个木板覆盖。而且是一个横着放的木板，一个竖着放的木板，那么所有横着的木板都看成x集合的点，竖着放的点都看成y集合的点。而格子看成边，那么这就是一个二分图求最小覆盖的问题了。

上代码

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn=59,inf=1e9;int n,m,ans;char a[maxn][maxn];int chk[maxn][maxn],tt;void coll(int t,int s,int tmp){    for(int i=s;i<=m;i++)    {        if(a[t][i]=='.') break;        chk[t][i]+=tmp;    }}void colc(int t,int s,int tmp){    for(int i=t;i<=n;i++)    {        if(a[i][s]=='.') break;        chk[i][s]+=tmp;    }}void show(){    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        printf("%d",chk[i][j]);        cout<<endl;    }}int mm(){    int aa=0,bb=0;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        if(!chk[i][j]&&a[i][j]=='*')        {            aa++;            break;        }    }    for(int i=1;i<=m;i++)    {        for(int j=1;j<=n;j++)        if(!chk[j][i]&&a[j][i]=='*')        {            bb++;            break;        }    }    return min(aa,bb);}void dfs(int t,int s,int ret){//    if(++tt>8000000) return ;//    show();//    cout<<ret<<endl<<endl;    if(ret+mm()>=ans) return ;    bool flag=true;    for(int i=t;i<=n&&flag;i++)    for(int j=1;j<=m&&flag;j++)    if(!chk[i][j]&&a[i][j]=='*')    {        if(a[i+1][j]!='*')        {            coll(i,j,1);            dfs(i,j,ret+1);            coll(i,j,-1);        }        else if(a[i][j+1]!='*')        {            colc(i,j,1);            dfs(i,j,ret+1);            colc(i,j,-1);        }        else        {            coll(i,j,1);            dfs(i,j,ret+1);            coll(i,j,-1);            colc(i,j,1);            dfs(i,j,ret+1);            colc(i,j,-1);        }        flag=false;    }    if(flag) ans=min(ret,ans);}int main(){//    freopen("in.txt","r",stdin);    while(scanf("%d %d",&n,&m)!=EOF)    {        tt=0;        for(int i=1;i<=n;i++) scanf("%s",&a[i][1]);        ans=inf;        memset(chk,0,sizeof(chk));        dfs(1,1,0);        cout<<ans<<endl;    }    return 0;}