[ZJOI 2007] 矩阵游戏

知识点

二分图匹配、增广路、排列等价

解题思路

把每行看成左点、每列看成右点，黑格连边。存在n条互不共享行列的黑格，当且仅当有完美匹配。对每行找增广路，匹配大小为n就输出Yes。

正确性说明

行列交换只改变位置，不改变每行每列相交的颜色；最后的黑色对角线对应原表中各占一行一列的n个黑格。反之完美匹配给每行指派不同列，按指派重排列即可使主对角线全黑。增广路算法逐次把匹配增至最大，故判定充分必要。

易错点

不能只检查每行每列至少有1个黑格；不同测试组清空匹配；输出Yes/No大小写一致。

复杂度

每组时间O(n³)，空间O(n²)，n≤200。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){int n;cin>>n;vector<vector<int>>g(n);for(int i=0;i<n;i++)for(int j=0,x;j<n;j++){cin>>x;if(x)g[i].push_back(j);}vector<int>match(n,-1),seen(n);function<bool(int)>dfs=[&](int u){for(int v:g[u])if(!seen[v]){seen[v]=1;if(match[v]<0||dfs(match[v])){match[v]=u;return true;}}return false;};int cnt=0;for(int i=0;i<n;i++){fill(seen.begin(),seen.end(),0);cnt+=dfs(i);}cout<<(cnt==n?"Yes":"No")<<'\n';}}