hdu1507

题解：

二分图最大匹配

建边和第一题差不多

每两个相邻的建边

然后输出方案

代码：

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdio>

using namespace std;

const int N=;

int vis[N],a[N][N],ans[N],map[N][N],g[N];

int k,n,m,sum,num;

struct node{int x,y;}p[N*N];

int dfs(int x)

{

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

     if (!vis[i]&&a[x][i])

      {

        vis[i]=;

        if (ans[i]==-||dfs(ans[i]))

         {

            ans[i]=x;

            return ;

         }

      }

       return ;

}

void match()

{

    sum=;

    memset(ans,-,sizeof(ans));

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

     {

        memset(vis,,sizeof(vis));

       if(dfs(i)) sum++;

     }

}

int main()

{

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

     {

        if (!n&&!m) break;

        int u,v;

        memset(a,,sizeof(a));

        memset(map,,sizeof(map));

        scanf("%d",&k);

        while (k--)

         {

            scanf("%d%d",&u,&v);

            map[u][v]=;

         }

        num=;

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

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

          if (map[i][j]==)

           {

            p[num].x=i;

            p[num++].y=j;

           }

        for (int l=;l<num;l++)

         for (int j=l+;j<num;j++)

          if ((abs(p[l].x-p[j].x)==&&p[l].y==p[j].y)

          ||(abs(p[l].y-p[j].y)==&&p[l].x==p[j].x))

           if ((p[l].x+p[l].y)%==)a[j][l]=;else a[l][j]=;

        match();

        printf("%d\n",sum);

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

         if (ans[i]!=-)

          printf("(%d,%d)--(%d,%d)\n",p[i].x,p[i].y,p[ans[i]].x,p[ans[i]].y);

        printf("\n");

     }

    return ;

}