二分图
匈牙利算法
重要的是怎么建图（怎么看都不像二分图....）
仔细看还是能发现的..
两个操作不管怎么搞，在同一行的永远在同一行，同一行的 1 想怎么左右换都可以
所以根本不用上下交换（如果下面没有1，换了以后上面就没有1了）
题目要让对角线上的每个点都有1
就是把对角线的点与 1 匹配
因为是对角线的点，所以可以发现：在矩阵中，如果这一列有一个 1 已经匹配了
那么这一列其他的 1 都不能与其他点匹配 ( 发现了吗，二分图中每个点同时也只能匹配一个点 )
所以把一列的看成一个点，与每行唯一需要匹配的点匹配（同样的，因为每行唯一所以也看成一个点）
如果要匹配，那么两个点必须要在同一行（显然...）
那么图就出来了，n 个对角线的点，n 列缩成 n 个点
如果第 i 行的第 j 列是 1，那么连一条从 i 到 j 的边
最后跑一遍模板就好了
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> using namespace std; const int N=100005;//数组可以开大点，最近因为数组大小不够死了很多次... int t,n,tot; int fir[N],from[N],to[N],cnt; inline void add(int a,int b) { from[++cnt]=fir[a]; fir[a]=cnt; to[cnt]=b; } int match[N]; bool vis[N]; inline bool dfs(int x) { for(int i=fir[x];i;i=from[i]) { int u=to[i]; if(vis[match[u]]) continue; vis[match[u]]=1; if((!match[u])||dfs(match[u])) { match[u]=x; return 1; } } return 0; }//以上为匈牙利模板 inline void Clear() { memset(match,0,sizeof(match)); memset(fir,0,sizeof(fir)); memset(from,0,sizeof(from)); memset(to,0,sizeof(to)); cnt=0; tot=0; }//有多组数据，每次都要初始化 int main() { int a; cin>>t; while(t--) { Clear(); scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&a); if(a) add(i,j); }//建图 bool flag=0; for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(!dfs(i)) { flag=1; break; } } if(flag) cout<<"No"<<endl; else cout<<"Yes"<<endl; } return 0; }