HDU 2819 Swap(二分图匹配)

HDU 2819 Swap(二分图匹配)

http://acm.hdu.edu.cn/showproblem.php?pid=2819

题意:

给定一个矩阵，矩阵元素取值为0或1，每次操作可以交换任意两行或两列，要求对于给定矩阵给出操作次数和操作序列将主对角线(A[i][i],i=1...n)元素全部变为1，无法满足则输出-1.

分析:

首先如果一个矩阵对于上述问题有解,那么该矩阵一定也能只通过交换行或只交换列来得到解.(该结论还不知道如何证⊙﹏⊙b.)

现在我们假设只交换行来得到解. 那么其实这个问题就是将原矩阵的初始n行重新分配给n个行号,且只有当初始第i行的第j列是1时,初始第i行才有资格被分配到新的第j行.(仔细体会一下这句话).

所以新的二分图左边的点集是初始的行号1-n,右边的点集是新的行号1-n. 且如果初始矩阵(i,j)格子是1,那么左i点就与右j点有一条无向边. 最终我们就是求这个二分图的最大匹配是否==n.(仔细想想是不是).如果等于n,则表示能通过交换得到解.反之,则不行.

假设所求二分图的最大匹配==n. 那么我们根据left数组可以得到一个匹配数组r[n](r[i]==j表初始的第i行应该放到新的第j行去).现在我们如何打印最终的交换序列呢?

我们只需要按选择排序的方式即可.假设当前我们处理第i行,且r[i]!=i(表示初始第i行不应该继续放在新的第i行),那么我们在r[i+1,n]范围内找到r[j]==i的这个j,然后swap(r[i],r[j])即可. 具体体会代码.

AC代码: 忘了打印交换次数,错了…悲剧

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn =100+10;

struct Max_Match
{
    int n;
    bool g[maxn][maxn];
    bool vis[maxn];
    int left[maxn];

    void init(int n)
    {
        this->n=n;
        memset(g,0,sizeof(g));
        memset(left,-1,sizeof(left));
    }

    bool match(int u)
    {
        for(int v=1;v<=n;v++)if(g[u][v] && !vis[v])
        {
            vis[v]=true;
            if(left[v]==-1 || match(left[v]))
            {
                left[v]=u;
                return true;
            }
        }
        return false;
    }

    int solve()
    {
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(match(i)) ans++;
        }
        return ans;
    }
}MM;

int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        MM.init(n);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int v;
            scanf("%d",&v);
            if(v) MM.g[i][j]=true;
        }

        if(MM.solve()==n)//有解
        {
            int r[maxn];
            for(int i=1;i<=n;i++) r[MM.left[i]]=i;
            int ans=0;
            int r1[maxn];//临时保存r的数组
            memcpy(r1,r,sizeof(r));
            for(int i=1;i<=n;i++)if(r1[i]!=i)
            for(int j=i+1;j<=n;j++)if(r1[j]==i)
            {
                ans++;
                swap(r1[i],r1[j]);
            }
            printf("%d\n",ans);
            for(int i=1;i<=n;i++)if(r[i]!=i)
            for(int j=i+1;j<=n;j++)if(r[j]==i)
            {
                printf("R %d %d\n",i,j);
                swap(r[i],r[j]);
            }
        }
        else printf("-1\n");
    }
    return 0;
}