题意:
判断一个黑白染色的棋盘能否通过交换行或列使对角线上都是黑色.
SOL:
真是有点醉...这种问题要么很神要么很水...第一眼感觉很水但就是不造怎么做...想了10分钟怎么感觉就是判断个数够不够n呢然后就蹦出了一个反例...然后就忍不了百度= =...
二分图匹配真是瞎了眼...然后发现好神又好水...
显然的同一行无论怎么交换都是同一行---->根本就没往这上面想...同一列永远都是同一列,那么只要判断有多少不同行又不同列的就好了...枚举有点虚,那么就匹配吧!按照行列建图,恩就是这样...
Code:
头文件都不要了= =
int head[maxn],now,point[maxm],next[maxm],match[maxn];
bool visit[maxn];
void add(int x,int y)
{
next[++now]=head[x];
head[x]=now;
point[now]=y;
}
int dfs(int k)
{
for(int i=head[k];i;i=next[i])if(!visit[point[i]])
{
int u=point[i];
visit[u]=1;
if(match[u]==-1||dfs(match[u]))
{
match[u]=k;
return 1;
}
}
return 0;
}
int main()
{
int t,n,x;
scanf("%d",&t);
while(t--)
{
now=0;
memset(head,0,sizeof(head));
int flag=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&x);
if(x==1)add(i,j);
}
memset(match,-1,sizeof(match));
for(int i=1;i<=n;i++)
{
memset(visit,0,sizeof(visit));
if(!dfs(i))
{
printf("No\n");
flag=1;break;
}
}
if(flag==0)printf("Yes\n");
}
return 0;
}