Swap
http://acm.hdu.edu.cn/showproblem.php?pid=2819
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的0 1矩阵，交换行或列使其主对角线（左对角线）都为1，问需要多少次交换，怎样交换
R a b表示第a行和第b行交换， C a b表示第a列和第b列交换
转换为二分匹配：
主对角线都为1即使G[a][b] = 1，此时a应该与b相等，a表示横坐标，b表示纵坐标（1<=a<=n, 1<=b<=n)
将横坐标存入集合X中将纵坐标存入集合Y中，（x，y）为1时，则x和y之间有一条连线，即x与y匹配
如果使主对角线都为1，则必须使其最大匹配等于n，否则就不能实现
当x == y但x与y不匹配时则交换,并记录如何交换,统计交换次数（即while(used[i] != i){a[j] = i;b[j] = used[i];swap(used[a[j]], used[b[j]]);j++})
无论是行交换还是列交换能得到结果的最终都能得到结果，但注意输出要保持一致
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define N 110
#define INF 0x3f3f3f3f using namespace std; int G[N][N], vis[N], used[N];
int n; bool Find(int u)//匈牙利算法
{
for(int i = ; i <= n ; i++)
{
if(!vis[i] && G[u][i])
{
vis[i] = ;
if(!used[i] || Find(used[i]))
{
used[i] = u;
return true;
}
}
}
return false;
} int main()
{
int a[], b[];
while(~scanf("%d", &n))
{
memset(G, , sizeof(G));
for(int i = ; i <= n ; i++)
for(int j = ; j <= n ; j++)
scanf("%d", &G[i][j]);
memset(used, , sizeof(used));
int ans = ;
for(int i = ; i <= n ; i++)
{
memset(vis, , sizeof(vis));
if(Find(i))
ans++;
}//求最大匹配
if(ans < n)
{
printf("-1\n"); continue;
}
int j = ;
for(int i = ; i <= n ; i++)
{
while(used[i] != i)//当横纵坐标相等但横坐标与纵坐标不匹配(这里注意是while而不是if,因为这个问题Wa了很多次，一直没发现）
{
a[j] = i;//a记录要交换的行
b[j] = used[i];//b记录要交换的列
swap(used[a[j]], used[b[j]]);//此时交换的并不是G里面的值，而是将匹配变了，则达到x与y匹配且x==y
j++;//统计要交换的次数
}
}
printf("%d\n", j);
for(int i = ; i < j ; i++)
printf("C %d %d\n", a[i], b[i]);//应为swap里是列交换所以这里输出“C”（used[i]表示i与used[i]匹配）
}
return ;
}