洛谷 P1129 [ZJOI2007]矩阵游戏（二分图匹配）
传送门
解题思路
我们可以先来到最终状态，第i,i位置都是黑色，然后考虑怎样可以转换过来，我们可以发现，当列与列交换时(a,b)(b,a)两个点可以通过a，b两列的交换得到正确的位置（a,a）(b,b)，所以我们现在就是要确定是否每一行都对应着独特的一列。
这就很显然了——二分图。
行为A，列为B，黑色的点就连边，最后判断最大匹配是否为n即可。
AC代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int t,n,m[205][205],vis[205],ok[205]; 6 bool work(int u){ 7 for(int i=1;i<=n;i++){ 8 if(m[u][i]&&!vis[i]){ 9 vis[i]=1; 10 if(!ok[i]||work(ok[i])){ 11 ok[i]=u; 12 return true; 13 } 14 } 15 } 16 return false; 17 } 18 int main() 19 { 20 cin>>t; 21 while(t--){ 22 memset(vis,0,sizeof(vis)); 23 memset(ok,0,sizeof(ok)); 24 memset(m,0,sizeof(m)); 25 cin>>n; 26 for(int i=1;i<=n;i++){ 27 for(int j=1;j<=n;j++){ 28 scanf("%d",&m[i][j]); 29 } 30 } 31 for(int i=1;i<=n;i++){ 32 memset(vis,0,sizeof(vis)); 33 if(!work(i)){ 34 cout<<"No"<<endl; 35 break; 36 } 37 if(i==n) cout<<"Yes"<<endl; 38 } 39 } 40 return 0; 41 }
//ZJOI2007 Day1 t3