hdu1507二分匹配

  1 //hdu1507 挺不错的题

 #include<stdio.h>

 #include<string.h>

 #define INF 99999999

 struct node

 {

     int x;

     int y;

 }rem[];

 struct Node

 {

     int v;

     int next;

 }edge[];

 int n,m,num,vis[],match[],map[][],mmark[],index,pre[];

 void add(int x,int y)

 {

     edge[index].v=y;

     edge[index].next=pre[x];

     pre[x]=index++;

 }

 void build(int x,int y,int a,int b)

 {

     int i,j;

     if(a<=||a>n||b<=||b>m||map[a][b]==)

         return ;

     else add(map[x][y],map[a][b]);

 }

 void test(int x,int y)

 {

     build(x,y,x-,y);

     build(x,y,x+,y);

     build(x,y,x,y-);

     build(x,y,x,y+);

 }

 void makemap()

 {

     int i,j;

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

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

         {

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

                 continue;

             test(i,j);

         }

 }

 int dfs(int u)

 {

     int i,j;

     for(i=pre[u];i!=-;i=edge[i].next)

     {

         int j=edge[i].v;

         if(!vis[j])

         {

             vis[j]=;

             if(match[j]==-||dfs(match[j]))

             {

                 match[j]=u;

                 return ;

             }

         }

     }

     return ;

 }

 int main()

 {

     int i,j,k;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         if(!n&&!m)break;

         scanf("%d",&k);

         memset(mmark,,sizeof(mmark));

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

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

                 map[i][j]=INF;

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

         {

             int x,y;

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

             map[x][y]=;

         }

         num=;

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

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

             {

                 if(map[i][j])

                 {

                     map[i][j]=num;

                     rem[num].x=i;

                     rem[num++].y=j;

                 }

             }

         /*for(i=1;i<=n;i++)

         {

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

                 printf("%d ",map[i][j]);

             printf("\n");

         }*/

         index=;

         memset(pre,-,sizeof(pre));

         makemap();

         /*for(i=1;i<num;i++)

         {

             for(j=1;j<num;j++)

             {

                 printf("%d ",g[i][j]);

             }

             printf("\n");

         }*/

         memset(match,-,sizeof(match));

         int ans=;

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

         {

             memset(vis,,sizeof(vis));

             if(dfs(i))

                 ans++;

         }

         int mark[];

         memset(mark,,sizeof(mark));

         printf("%d\n",ans/);

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

         {

             if(!mark[i]&&!mark[match[i]]&&match[i]!=-)

             {

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

                 mark[i]=;mark[match[i]]=;

             }

         }

         printf("\n");

     }

 }

 /*

 3 3

 4

 2 3

 1 3

 3 2

 1 2

 4 5

 6

 1 2

 1 3

 3 5

 3 4

 4 2

 2 5

 */