HDU2819 Swap 二分图匹配

由于没有输出交换多少次，贡献了无数次 system error。求解该题相当与给每一行找到一个1对应出现的位置，在排序就可以了。

代码如下：

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cstring>
#define MAXN 105
using namespace std;

int N, G[MAXN][MAXN], marry[MAXN], visit[MAXN];

int r1[MAXN], r2[MAXN], count;

int path(int u)
{
    for (int i = 1; i <= N; ++i) {
        if (!G[u][i] || visit[i])
            continue;
        visit[i] = 1;
        if (!marry[i] || path(marry[i])) {
            marry[i] = u;
            return 1;
        }
    }   
    return 0;
}

void Accepted()
{
    int x;
    for (int i = 1; i <= N; ++i) {
        x = i;
        for (int j = i; j <= N; ++j) {
            if (marry[j] < marry[x]) {
                x = j;
            }
        } 
        if (x != i) {
            r1[++count] = i, r2[count] = x;
            int t = marry[i];
            marry[i] = marry[x];
            marry[x] = t; 
        }     
    }
}

int main()
{
    int x, cnt;
    while (scanf("%d", &N) == 1) {
        cnt = 0;
        count = 0;
        memset(G, 0, sizeof (G));
        memset(marry, 0, sizeof (marry));
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                scanf("%d", &x);
                if (x) {
                    G[i][j] = 1;
                }
            }
        }
        for (int i = 1; i <= N; ++i) {
            memset(visit, 0, sizeof (visit));
            if (path(i))
                ++cnt;
        }
        if (cnt != N)
            puts("-1");
        else {
            Accepted();
            printf("%d\n", count);
            for (int i = count; i >= 1; --i)
                printf("R %d %d\n", r1[i], r2[i]);
        }
    }
    return 0;
}