二分图

匈牙利算法

重要的是怎么建图（怎么看都不像二分图....）

仔细看还是能发现的..

两个操作不管怎么搞，在同一行的永远在同一行，同一行的 1 想怎么左右换都可以

所以根本不用上下交换（如果下面没有1，换了以后上面就没有1了）

题目要让对角线上的每个点都有1

就是把对角线的点与 1 匹配

因为是对角线的点，所以可以发现：在矩阵中，如果这一列有一个 1 已经匹配了

那么这一列其他的 1 都不能与其他点匹配 ( 发现了吗，二分图中每个点同时也只能匹配一个点 )

所以把一列的看成一个点，与每行唯一需要匹配的点匹配（同样的，因为每行唯一所以也看成一个点）

如果要匹配，那么两个点必须要在同一行（显然...）

那么图就出来了，n 个对角线的点，n 列缩成 n 个点

如果第 i 行的第 j 列是 1，那么连一条从 i 到 j 的边

最后跑一遍模板就好了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          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"<