Swap[HDU2819]

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

Problem 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
2
0 1
1 0
2
1 0
1 0

Sample Output
1
R 1 2
-1

　　题意：给定一个n*n的01矩阵，要求通过若干次行交换或列交换来满足主对角线上的数字均为1。

　　首先能确定的一点，只用行交换或只用列交换就能满足。一开始看到跟覆盖有关，还在想会不会是舞蹈链什么的，后来发现并不需要。可以把对角线上某一点为1理解为行与列的匹配，这样行和列就正好构成了一个二分图。如果这个二分图的最大匹配为n的话就存在方案，此时，根据匈牙利算法的匹配数组就能找到解法。

#include <stdio.h>
#include <string.h>

int a[105], b[105];
class Hungary {
#define Hungary_MAX_Node 105
#define Hungary_MAX_Edge 10005
public:
    struct EDGE {
        int v;
        int next;
    } edge[Hungary_MAX_Edge];
    int head[Hungary_MAX_Node];
    int Left[Hungary_MAX_Node];
    bool vis[Hungary_MAX_Node];
    int N, M;
    Hungary() {
        clear();
    }
    void clear() {
        N = M = 0;
        memset(Left, 0, sizeof(Left));
        memset(head, -1, sizeof(head));
    }
    void addEdge(int a, int b) {
        edge[M].v = b;
        edge[M].next = head[a];
        head[a] = M++;
    }
    bool dfs(int u) {
        for (int e = head[u]; e != -1; e = edge[e].next) {
            int v = edge[e].v;
            if (!vis[v]) {
                vis[v] = true;
                if (!Left[v] || dfs(Left[v])) {
                    Left[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    int Max_Match() {
        int ret = 0;
        for (int i = 1; i <= N; i++) {
            memset(vis, 0, sizeof(vis));
            if (dfs(i)) {
                ret++;
            }
        }
        return ret;
    }
};
Hungary hungary;
int main() {
    int N;
    while (~scanf("%d", &N)) {
        hungary.clear();
        hungary.N = N;
        int x, ans;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++) {
                scanf("%d", &x);
                if (x) {
                    hungary.addEdge(i, j);
                }
            }
        ans = hungary.Max_Match();
        if (ans < N) {
            printf("-1
");
            continue;
        }
        int tot = 0, j;
        for (int i = 1; i <= N; i++) {
            for (j = 1; j <= N && hungary.Left[j] != i; j++);
            if (i != j) { 
                a[tot] = i;
                b[tot] = j;
                tot++;
                int t = hungary.Left[i];
                hungary.Left[i] = hungary.Left[j];
                hungary.Left[j] = t;
            }
        }
        printf("%d
", tot);
        for (int i = 0; i < tot; i++) {
            printf("C %d %d
", a[i], b[i]);
        }
    }
    return 0;
}