思路：脑子+二分图匹配 

提交：1次（课上讲过）

题解：

发现：如果符合题意，那么行和列一定是一一匹配的（必要条件），所以最大匹配必须是$n$。

同时我们发现，一定可以通过交换行列的方式，将（看起来）有交错的最大匹配，转换成符合题意的状态。

所以最大匹配是$n$即为判断依据。

 

#include
     
      #include
      
       #include
       
        #include
        
         #define R register intusing namespace std;#define ull unsigned long long#define ll long long#define pause (for(R i=1;i<=10000000000;++i))#define IN freopen("NOIPAK++.in","r",stdin)#define OUT freopen("out.out","w",stdout)namespace Fread {    static char B[1<<15],*S=B,*D=B;#ifndef JACK    #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)#endif    inline int g() {        R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;        do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;    } inline bool isempty(const char& ch) {
   return ch<=36||ch>=127;}    inline void gs(char* s) {register char ch; while(isempty(ch=getchar())); do *s++=ch; while(!isempty(ch=getchar()));}}using Fread::g; using Fread::gs;const int N=210;int vis[N],pre[N],t,ans,n,tim; bool e[N][N];inline bool dfs(int u) {    for(R v=1;v<=n;++v) if(e[u][v]&&vis[v]!=tim) {        vis[v]=tim; if(!pre[v]||dfs(pre[v])) {pre[v]=u; return true ;}    } return false;}signed main() {#ifdef JACK#endif    t=g(); while(t--) { ans=0,tim=0;        memset(vis,0,sizeof(vis)),memset(pre,0,sizeof(pre)),memset(e,false,sizeof(e));        n=g(); for(R i=1;i<=n;++i) for(R j=1;j<=n;++j) e[i][j]=g();        for(R i=1;i<=n;++i) ++tim,ans+=dfs(i);        if(ans==n) printf("Yes\n");        else printf("No\n");    }}
        
       
      
     

---

2019.07.18