hdu4185

题解：
每两个联通的油井建边

然后二分图最大匹配

最后答案除以2

代码：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

char c;

int T,a[N/][N/],f[N],match[N],fi[N],cas,num,ne[N],zz[N],n,cnt;

int dfs(int x)

{

    for (int i=fi[x];i;i=ne[i])

     if (!f[zz[i]])

      {

          f[zz[i]]=;

          if (!match[zz[i]]||dfs(match[zz[i]]))

           {

               match[zz[i]]=x;

               return ;

           }

      }

    return ;

}

void jb(int x,int y)

{

    ne[++num]=fi[x];

    fi[x]=num;

    zz[num]=y;

    ne[++num]=fi[y];

    fi[y]=num;

    zz[num]=x;

}

int main()

{

    scanf("%d",&T);

    while (T--)

     {

         memset(a,,sizeof a);

         memset(fi,,sizeof fi);

         num=;

         scanf("%d",&n);

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

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

           {

               int ch=getchar();

               while (ch!='.'&&ch!='#')ch=getchar();

               if (ch=='#')a[i][j]=++cnt;

               else a[i][j]=;

           }

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

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

          if (a[i][j])

           {

               if (a[i+][j])jb(a[i][j],a[i+][j]);

               if (a[i][j+])jb(a[i][j],a[i][j+]);

           }

        int ans=;

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

         {

             memset(f,,sizeof f);

             ans+=dfs(i);

         }

        printf("Case %d: %d\n",++cas,ans/);

     }

    return ;

}