hdu 2819 Swap

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

0 1

1 0

Sample Output

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 = 1 ; i <= n ; i++)
    {
        if(!vis[i] && G[u][i])
        {
            vis[i] = 1;
            if(!used[i] || Find(used[i]))
            {
                used[i] = u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int a[1010], b[1010];
    while(~scanf("%d", &n))
    {
        memset(G, 0, sizeof(G));
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= n ; j++)
                scanf("%d", &G[i][j]);
        memset(used, 0, sizeof(used));
        int ans = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            memset(vis, 0, sizeof(vis));
            if(Find(i))
                ans++;
        }//求最大匹配
        if(ans < n)
        {
            printf("-1
");

            continue;
        }
        int j = 0;
        for(int i = 1 ; 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
", j);
        for(int i = 0 ; i < j ; i++)
            printf("C %d %d
", a[i], b[i]);//应为swap里是列交换所以这里输出“C”（used[i]表示i与used[i]匹配）
    }
    return 0;
}

View Code