hdoj 2819 Swap (最大匹配+输出路径)

题意：

给你一个每位是0或1的矩阵，问你是否可以经过交换行和交换列使矩阵的对角线都为1，如果可以输出交换的方法。

思路：

行和列的匹配，左边是行，右边是列，然后如果行列交点是1，那么就可以匹配，看是否为完美匹配，然后输出怎么交换的。

输出交换的路径：

可以锁定行，来选择列和它匹配，将选择的列移动到和该行形成对角线上是1的位置，比如和第一行匹配的列，就要移动要第一列，第二行的，就到第二列。其实就是对第i行，找一个第i个数是1的列和它匹配，然后看是否是最大匹配！

代码：

#include<bits/stdc++.h>using namespace std;const int maxn = 105;vector<int> e[maxn];int n, match[maxn], vis[maxn], ans1[maxn], ans2[maxn];bool dfs(int x){    for(int i = 0; i < e[x].size(); i++)    {        int to = e[x][i];        if(!vis[to])        {            vis[to] = 1;            if(!match[to] || dfs(match[to]))            {                match[to] = x;                return true;            }        }    }    return false;}int Hungary(){    int res = 0;    for(int i = 1; i <= n; i++)    {        memset(vis, 0, sizeof(vis));        res += dfs(i);    }    return res;}int main(void){    while(cin >> n)    {        memset(match, 0, sizeof(match));        for(int i = 1; i < maxn; i++)            e[i].clear();        for(int i = 1; i <= n; i++)            for(int j = 1; j <= n; j++)            {                int t;                scanf("%d", &t);                if(t) e[i].push_back(j);            }        if(Hungary() != n) puts("-1");        else        {            int cnt = 0;            for(int i = 1; i <= n; i++)            {                int pos;                for(int j = 1; j <= n; j++)                    if(match[j] == i)                    {                        pos = j;                        break;                    }                if(pos != i)                {                    ans1[cnt] = i;                    ans2[cnt++] = pos;                    swap(match[i], match[pos]);                }            }            PRintf("%d/n", cnt);            for(int i = 0; i < cnt; i++)                printf("C %d %d/n", ans1[i], ans2[i]);        }    }    return 0;}
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?InputThere 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.OutputFor 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
20 11 021 01 0Sample Output
1R 1 2-1