hdu 1507 记录路径的二分匹配 **

时间：2023-01-25 08:05:43

题意：N*M的矩形，向其中填充1*2的小块矩形，黑色的部分不能填充，问最多可以填充多少块。
链接：点我
黑白棋最大匹配
将棋盘中i+j为奇数的做A集合，偶数的做B集合，相邻的则建立联系。于是便转换成寻找最大匹配的问题

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 typedef long long ll;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int a[][];

 int b[];

 int n,m,tt;

 /* ***********************************************************

 //二分图匹配（匈牙利算法的DFS实现）(邻接矩阵形式)

 //初始化：g[][]两边顶点的划分情况

 //建立g[i][j]表示i->j的有向边就可以了，是左边向右边的匹配

 //g没有边相连则初始化为0

 //uN是匹配左边的顶点数，vN是匹配右边的顶点数

 //调用：res=hungary();输出最大匹配数

 //优点：适用于稠密图，DFS找增广路，实现简洁易于理解

 //时间复杂度:O(VE)

 //************************************************************ */

 //顶点编号从0开始的

 int uN,vN;//u,v的数目，使用前面必须赋值

 int g[MAXN][MAXN];//邻接矩阵

 int linker[MAXN];

 bool used[MAXN];

 bool dfs(int u)

 {

     for(int v = ; v < vN;v++)

     if(g[u][v] && !used[v])

     {

         used[v] = true;

         if(linker[v] == - || dfs(linker[v]))

         {

             linker[v] = u;

             return true;

         }

     }

     return false;

 }

 int hungary()

 {

     int res = ;

     memset(linker,-,sizeof(linker));

     for(int u = ;u < uN;u++)

     {

         memset(used,false,sizeof(used));

         if(dfs(u))res++;

     }

     return res;

 }

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

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

     {

         if(n==&&m==)  break;

         scanf("%d",&k);

         int u,v;

         cl(a);

         while(k--)

         {

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

             u--,v--;

             a[u][v]=-;

         }

         int tot=;

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

         {

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

             {

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

                 {

                     b[tot]=i*m+j;

                     a[i][j]=tot++;

                 }

             }

         }

         cl(g);

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

         {

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

             {

                 if(a[i][j]!=-&&((i+j)%==))

                 {

                     int w=a[i][j];

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

                         g[w][a[i-][j]]=;

                     if(i<n-&&a[i+][j]!=-)

                         g[w][a[i+][j]]=;

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

                         g[w][a[i][j-]]=;

                     if(j<m-&&a[i][j+]!=-)

                         g[w][a[i][j+]]=;

                 }

             }

         }

         vN=uN=tot;

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

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

         {

             if(linker[i]!=-)

             {

                 int x1=b[i]/m;

                 int y1=b[i]%m;

                 int x2=b[linker[i]]/m;

                 int y2=b[linker[i]]%m;

                 printf("(%d,%d)--(%d,%d)\n",x1+,y1+,x2+,y2+);

             }

         }

         printf("\n");

     }

 }

相关文章