POJ2226Muddy Fields

题目：http://poj.org/problem?id=2226

巧妙建图：以行或列上的联通块作为点，每个泥格子作为边，求最小点覆盖就可以了！

于是用匈牙利算法找最大匹配。注意要对右部点记录每一个左部点的vis！

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int n=,N=((n*n)<<);

int r,c,head[N],xnt=,stack[n],top,cnt,col[n][n],pre[N],knt;

char ch[n][n];

bool vis[N];

struct Edge{

    int next,to;

    Edge(int n=,int t=,int c=):next(n),to(t) {}

}edge[N];

bool check(int cur)

{

    for(int i=head[cur],v;i;i=edge[i].next)

        if(!vis[v=edge[i].to])

        {

            vis[v]=;

            if(!pre[v=edge[i].to]||check(pre[v]))

            {pre[v]=cur;/*printf("cur=%d v=%d\n",cur,v);*/return true;}

        }

    return false;

}

void cz1(int i)

{

    cnt++;

    while(ch[i][stack[top]]=='*')col[i][stack[top--]]=cnt;

}

void cz2(int i)

{

    cnt++;

    while(ch[stack[top]][i]=='*')

    {

        edge[++xnt]=Edge(head[col[stack[top]][i]],cnt);

//        printf("%d %d\n",col[stack[top]][i],cnt);

        head[col[stack[top--]][i]]=xnt;

    }

}

int main()

{

    scanf("%d%d",&r,&c);

    for(int i=;i<=r;i++)

    {

        getchar();

        for(int j=;j<=c;j++)

        {

            scanf("%c",&ch[i][j]);

            if(ch[i][j]=='*')stack[++top]=j;

            else if(top)cz1(i);

        }

        if(top)cz1(i);

        top=;

    }

//    for(int i=1;i<=r;i++)

//    {

//        for(int j=1;j<=c;j++)

//            printf("%d",col[i][j]);printf("\n");

//    }

    int lm=cnt;

    for(int i=;i<=c;i++)

    {

        for(int j=;j<=r;j++)

        {

            if(ch[j][i]=='*')stack[++top]=j;

            else if(top)cz2(i);

        }

        if(top)cz2(i);

        top=;

    }

    for(int i=;i<=lm;i++)

    {

        memset(vis,,sizeof vis);//万一同一次踩在同一个未匹配右部点的话

        if(check(i))knt++;    //右边不会主动匹配左边 ，这个i一定未匹配

    }

    printf("%d",knt);

    return ;

}