hdu2819 Swap 最大匹配（难题）

题目大意：

　　给定一个元素的值只有1或者0的矩阵，每次可以交换两行（列），问有没有方案使得对角线上的值都是1。题目没有限制需要交换多少次，也没限制行交换或者列交换，也没限制是主对角线还是副对角线。虽然没限制，但是解法都是差不多的。

　　这是09年的多校题目，对一般人来说，不看解题报告是无法做出来的。我是那种看了解题报告也没做出来，然后看了好几遍才看懂的人。

　　http://www.cnblogs.com/jzlikewei/archive/2012/07/09/2583608.html

解题思路：

　　对于二分图模型｛X，Y| E｝，我们可以把行作为X集合里的点，把列作为Y集合里的点，边就是值为满足MAP[x][y]=1的条件。判断有没有解就是判断所有的行有没有匹配，也就是最大匹配是否等于n。

　　按照顺序输出交换的行(或者是列)是通过而一个二重循环。比如说：从第一行开始，如果它与匹配的列不相等（对角线需要行列相等），就从第二行开始找，直到找到匹配的列等于1。然后把此行匹配的列改为第一行匹配的列。一直下去。因为没有要求最小交换次数的解，所以这样暴力求解就可以了。

　　在一般的求最大匹配的模版中，都会有数组cx[],cx[]。其中cx[]记录与X集合匹配的Y集合中元素的标号，cy[]是记录与Y集合匹配的X集合中元素的标号。比如说,cx[3]=2的意思是与X集合中3号元素匹配的Y的集合的元素的编号是2。这两个数组一般情况下只要一个就够的，有些题目就需要输出匹配的序列。

下面的我的代码：Hopcroft-Karp算法，代码有点长，时间复杂度低。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=,INF=0x3f3f3f3f;

 int cx[N],cy[N],dx[N],dy[N],bmap[N][N];

 bool bmask[N];

 int nx,ny,dis,ans;

 bool searchpath()

 {

     queue<int> q;

     dis=INF;

     memset(dx,-,sizeof(dx));

     memset(dy,-,sizeof(dy));

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

     {

         if(cx[i]==-){ q.push(i); dx[i]=; }

         while(!q.empty())

         {

             int u=q.front(); q.pop();

             if(dx[u]>dis) break;

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

             {

                 if(bmap[u][v]&&dy[v]==-)

                 {

                     dy[v]= dx[u] + ;

                     if(cy[v]==-) dis=dy[v];

                     else

                     {

                         dx[cy[v]]= dy[v]+;

                         q.push(cy[v]);

                     }

                 }

             }

         }

     }

     return dis!=INF;

 }

 int findpath(int u)

 {

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

     {

         if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+)

         {

             bmask[v]=;

             if(cy[v]!=-&&dy[v]==dis) continue;

             if(cy[v]==-||findpath(cy[v]))

             {

                 cy[v]=u; cx[u]=v;

                 return ;

             }

         }

     }

     return ;

 }

 void maxmatch()

 {

     ans=;

     memset(cx,-,sizeof(cx));

     memset(cy,-,sizeof(cy));

     while(searchpath())

     {

         memset(bmask,,sizeof(bmask));

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

             if(cx[i]==-) ans+=findpath(i);

     }

 }

 struct node

 {

     int x,y;

 }e[N];

 int main()

 {

     //freopen("test.txt","r",stdin);

     int cas,i,j,k,n;

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

     {

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

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

                 scanf("%d",&bmap[i][j]);

         nx=ny=n;

         maxmatch();

         if(ans<n) {printf("-1\n");continue;}

         k=;

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

             if(cx[i]!=i){

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

                     if(cx[j]==i){

                         e[k].x=i;e[k++].y=j;

                         cx[j]=cx[i];

                         break;

                     }

                 }

             }

         }

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

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

             printf("R %d %d\n",e[i].x,e[i].y);

     }

     return ;

 }

巴特西

hdu2819 Swap 最大匹配（难题）

最新文章

热门文章