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[], b[];
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 = ;
memset(Left, , sizeof(Left));
memset(head, -, 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 != -; 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 = ;
for (int i = ; i <= N; i++) {
memset(vis, , 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 = ; i <= N; i++)
for (int j = ; j <= N; j++) {
scanf("%d", &x);
if (x) {
hungary.addEdge(i, j);
}
}
ans = hungary.Max_Match();
if (ans < N) {
printf("-1\n");
continue;
}
int tot = , j;
for (int i = ; i <= N; i++) {
for (j = ; 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\n", tot);
for (int i = ; i < tot; i++) {
printf("C %d %d\n", a[i], b[i]);
}
}
return ;
}