HDU2819：Swap（二分图匹配）

Swap

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4932 Accepted Submission(s): 1836
Special Judge

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2819

Description:

Given an N*N matrix with each entry equal to 0 or 1. You can swap any two rows or any two columns. Can you find a way to make all the diagonal entries equal to 1?

Input:

There are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix.

Output:

For each test case, the first line contain the number of swaps M. Then M lines follow, whose format is “R a b” or “C a b”, indicating swapping the row a and row b, or swapping the column a and column b. (1 <= a, b <= N). Any correct answer will be accepted, but M should be more than 1000.

If it is impossible to make all the diagonal entries equal to 1, output only one one containing “-1”.

Sample Input:

0 1

1 0

Sample Output:

1
R 1 2
-1

题意：

通过交换行和列，使左上角到右下角的对角线都为1。

题解：

左上角到右下角的对角线坐标为(i,i)，横纵坐标相等，这是一个特性。我们要做的就是通过交换，使1的横纵坐标相等。

考虑最终的情况，对角线上的1横纵坐标都相等，这在二分图中，就相当于1-1,2-2...n-n，相当于两边集合都是平行相连的。

通过这里可以想到二分图的最大匹配就为n，如果小于n，无论怎样，都不能做到一一平行相连。

那么可行性就可以通过二分图最大匹配判定。

输出方案还是挺有意思的，最终的状态是平行相连，那么我就考虑dfs过后的match数组，不水平的连成水平就行了。

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

const int N =  ;

int map[N][N],link[N][N],match[N],check[N],r[N],a[N],b[N];

int n,ans,tot;

inline void init(){

    memset(map,,sizeof(map));memset(link,,sizeof(link));

    memset(match,-,sizeof(match));ans=;tot=;

    memset(a,,sizeof(a));memset(b,,sizeof(b));

}

inline int dfs(int x){

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

        if(link[x][i] && !check[i]){

            check[i]=;

            if(match[i]==- || dfs(match[i])){

                match[i]=x;

                return ;

            }

        }

    }

    return ;

}

inline void Swap(){

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

        if(match[i]!=i){

            a[++tot]=i;b[tot]=match[i];

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

                if(match[j]==i){

                    swap(match[i],match[j]);

                    break ;

                }

            }

        }

    }

}

int main(){

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

        init();

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

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

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

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

            }

        }

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

            memset(check,,sizeof(check));

            if(dfs(i)) ans++;

        }

        if(ans!=n){

            puts("-1");continue ;

        }

        Swap();

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

        for(int i=;i<=tot;i++) printf("R %d %d\n",a[i],b[i]);

    }

    return ;

}