HDU 2819 Swap(Bipartite graph match)

Description

给出N * N的01矩阵，能否交换行列使得最终主对角线上全为1，不能的话输出-1，能的话输出方案.

Analyze

刚开始想的时候，不明白怎么换，想着什么情况下既要换行又要换列，是那种情况的话该怎么换？越想越复杂。看了题解：

若可以，只换行可行，只换列也可行

二分图最大匹配等于n则可以

DFS(int x)时 link[i] = x；是标记列i被分配给x，是列被标记了！

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;

int n, mp[N][N], link[N];

bool vis[N];
bool DFS(int x)
{
    for(int i = 1; i <= n; ++i)
        if(mp[x][i] && !vis[i])
        {
            vis[i] = 1;
            if(link[i] == -1 || DFS(link[i]))
            {
                link[i] = x;
                return 1;
            }
        }
    return 0;
}

int Match()
{
    int res = 0;
    for(int i = 1; i <= n; ++i)
    {
        memset(vis, 0, sizeof(vis));
        if(DFS(i))
            res++;
    }
    return res;
}

int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                scanf("%d", &mp[i][j]);

        memset(link, -1, sizeof(link));
        int matches = Match();

        if(matches != n)
        {
            cout << "-1\n";
            continue;
        }

        int L[N], R[N], num = 0;
        for(int i = 1; i <= n; ++i)
            if(i != link[i])
                for(int j = 1; j <= n; ++j)
                    if(link[j] == i)
                    {
                        L[num] = i, R[num] = j;
                        num++, swap(link[i], link[j]);
                        break;
                    }
        cout << num << '\n';
        for(int i = 0; i < num; ++i)
            printf("C %d %d\n", L[i], R[i]);
    }
    return 0;
}