poj2446

题解：

二分图匹配

看看是否能达到目标

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=;

int num,ne[N],fi[N],zz[N],k,cnt,a[][],f[N],match[N],x,y,n,m;

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 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 ;

}

int main()

{

    while (~scanf("%d%d%d",&m,&n,&k))

     {

         memset(fi,,sizeof fi);

        memset(a,,sizeof a);

        memset(match,,sizeof match);

        num=cnt=;

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

          {

             scanf("%d%d",&x,&y);

             a[y][x]=-;

          }

         if ((n*m-k)%)

         {

             puts("NO");

             continue;

         }

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

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

          if (!a[i][j])a[i][j]=++cnt;

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

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

            if (a[i][j]!=-)

              {

               if (a[i+][j]!=-&&i!=m)jb(a[i][j],a[i+][j]);

               if (a[i][j+]!=-&&j!=n)jb(a[i][j],a[i][j+]);

              }

        int ans=;

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

          {

             memset(f,,sizeof f);

             ans+=dfs(i);

          }

        ans/=;

        if (ans*==cnt)puts("YES");

        else puts("NO");

     }

}