题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1059

题目分类：二分图匹配，网络流

题意：

给出一个01矩阵，每次允许交换任意两行或任意两列，问能否使得结果的矩阵中一条对角线全部为1。【对别的位置没有要求】

题解：

可以发现无论如何操作，原来在同一行的还在同一行，原来在同一列的还在同一列，所以把问题转化为问矩阵中能否找到n个点使得这n个点的横坐标为1~n，纵坐标也是1~n。

然后就是二分图匹配。

程序：

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxl=20000;
int st[maxl],ed;
struct node
{
    int next,to,fl,opt;
}g[10*maxl];
inline void add(int x,int y,int z)
{
//	printf("%d %d %d\n",x,y,z);
    ed++;
    g[ed].to=y;
    g[ed].next=st[x];
    g[ed].fl=z;
    g[ed].opt=ed+1;
    st[x]=ed;
    ed++;
    g[ed].to=x;
    g[ed].next=st[y];
    g[ed].fl=0;
    g[ed].opt=ed-1;
    st[y]=ed;
}
int x1,x2,x3,lev[maxl],des;
inline bool makelev()
{
    queue<int>q;
    q.push(0);
    memset(lev,-1,sizeof(lev));
    lev[0]=1;
    while (!q.empty())
    {
        x1=q.front();q.pop();//printf("%d ",x1);
        for (int i=st[x1];i!=0;i=g[i].next)
        {
            if(lev[g[i].to]==-1&&g[i].fl!=0)
            {
                q.push(g[i].to);
                lev[g[i].to]=lev[x1]+1;
                if(g[i].to==des){return true;}
            }
        }
    }return false;
}
int stap,sta[maxl],spre[maxl],stae[maxl];
int maxflow;
inline void extend()
{
    int del;
    stap=1;
    sta[1]=0;
    for (int i=0;i<=des;i++)
    {
        spre[i]=st[i];//printf("%d %d\n",i,st[i]);
    }
    while (stap!=0)
    {
        x1=sta[stap];
    //  printf("%d\n",x1);
        if(x1!=des)
        {
            for (;spre[x1]!=0;spre[x1]=g[spre[x1]].next)
            {
                if(g[spre[x1]].fl!=0&&lev[x1]+1==lev[g[spre[x1]].to])
                {
                    break;
                }
            }
            if(spre[x1]!=0)
            {
                stap++;
                stae[stap]=spre[x1];
                sta[stap]=g[spre[x1]].to;
            }
            else
            {
                stap--;lev[x1]=0;
            }
        }
        else
        {
            del=1050000000;
            for (int i=stap;i>=2;i--)
            {
                del=min(del,g[stae[i]].fl);
            }//printf("%d\n",del);
            maxflow+=del;
            for (int i=stap;i>=2;i--)
            {
                g[stae[i]].fl-=del;
                g[g[stae[i]].opt].fl+=del;
                if(g[stae[i]].fl==0)stap=i-1;
            }
        }
    }
}
inline void dinic()
{
    maxflow=0;
    while (makelev())extend();
}
int n,m,ff;
int main()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		ed=0;
		des=n+n+1;
		memset(st,0,sizeof(st));
		for (int i=1;i<=n;i++)
		{
			add(0,i,1);
			add(i+n,des,1);
			for (int j=1;j<=n;j++)
			{
				scanf("%d",&ff);
				if(ff==1)add(i,j+n,1);
			}
		}
		dinic();
		if(maxflow==n)printf("Yes\n");
		else printf("No\n");
	}
    return 0;
}