P1129 [ZJOI2007] 矩阵游戏

P1129 [ZJOI2007] 矩阵游戏

大意

给你一个矩阵的黑白情况，求是否能通过交换行和列达到主对角线上全是黑点。

思路

由于行的这个点用了就不能用这个列移动了，于是我们考虑从这个点的行向列连边，跑二分图匹配。

实际上在最终情况中就是每个行都匹配了一个列。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 300;
vector<int> g[N];
bool vst[N];
int rmatch[N];
bool dfs(int u) {for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (!vst[v]) {vst[v] = true;if(rmatch[v] == -1 || dfs(rmatch[v])){rmatch[v] = u;return true;}}}return false;
}
int hungary(int n) {int cnt = 0;memset(rmatch, -1, sizeof(rmatch));for (int i = 1; i <= n; ++i) {memset(vst, 0, sizeof(vst));cnt += dfs(i);}return cnt;
}
int main() {int T, n, x;cin >> T;while (T--) {cin >> n;for (int i = 1; i <= n; i++) g[i].clear();for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> x;if(x == 1){g[i].push_back(j);}}}if(hungary(n) == n){cout << "Yes\n";}else{cout << "No\n";}}return 0;
}