矩阵游戏 匈牙利算法

题意

给定一个的01方阵，问是否能够通过行交换和列交换使得主对角线上都是1.

思路

主对角线上都是1，这一条件等价于：对于每一行，都有唯一的与之对应的列上是。

即可转化为匈牙利算法。

Solution

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
using namespace std;
const int N = 210;
//匈牙利算法O(n^3)
int n;
int g[N][N];  // graph 描述图关系
bool vis[N];
int link[N];

bool dfs(int x) {
    for (int i = 1; i <= n; i++) {  //遍历
        if (!vis[i] && g[x][i]) {   //如果存在关系且没有被访问过
            vis[i] = 1;             //访问记录
            if (!link[i] || dfs(link[i])) {  //如果名花无主或者可以挪动
                link[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    int T;
    sc(T);
    while (T--) {
        sc(n);
        memset(link, 0, sizeof link);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) sc(g[i][j]);
        bool f = 1;
        for (int i = 1; i <= n && f; i++) {
            memset(vis, 0, sizeof(vis));
            if (!dfs(i)) f = 0;
        }
        puts(f ? "Yes" : "No");
    }
    return 0;
}