AcWing 2267. 矩阵游戏(匈牙利算法)
原题链接
困难
作者:
殇ベ_11
,
2021-05-22 09:49:01
,
所有人可见
,
阅读 289
题目描述
小 Q 是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。
矩阵游戏在一个 N×N 黑白方阵进行(如同国际象棋一般,只是颜色是随意的)。
每次可以对该矩阵进行两种操作:
行交换操作:选择矩阵的任意两行,交换这两行(即交换对应格子的颜色)
列交换操作:选择矩阵的任意行列,交换这两列(即交换对应格子的颜色)
游戏的目标,即通过若干次操作,使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
对于某些关卡,小 Q 百思不得其解,以致他开始怀疑这些关卡是不是根本就是无解的!!
于是小 Q 决定写一个程序来判断这些关卡是否有解。
输入格式
第一行包含一个整数 T,表示数据的组数。
接下来包含 T 组数据,每组数据第一行为一个整数 N,表示方阵的大小;
接下来 N 行为一个 N×N 的 01 矩阵(0 表示白色,1 表示黑色)。
输出格式
包含 T 行。
对于每一组数据,如果该关卡有解,输出一行 Yes;否则输出一行 No。
数据范围
1≤N≤200
样例
输入样例:
2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0
输出样例:
No
Yes
算法1
C++ 代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5;
int T;
int n,m;
int res;
int head[N],idx = 0;
int match[N];
bool vis[N];
struct edge{
int to;
int next;
}e[N];
void add(int u,int v)
{
e[++idx].to = v;
e[idx].next = head[u];
head[u] = idx;
}
void clear(){
T-- ;
res = 0 ;
for( int i = 1 ; i<= idx ; i++ )
e[i].to = head[i] = e[i].next = 0;
idx = 1 ;
for( int i = 1 ; i <= 2*n ; i++ ){
match[ i ] = 0 ;
}
}
int find(int u)
{
for(int i = head[u]; i;i = e[i].next)
{
int v = e[i].to;
if(!vis[v])
{
vis[v] = true;
if(!match[v] || find(match[v]))
{
match[v] = u;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d",&T);
while(T != 0){
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= n;j ++){
int m;
scanf("%d",&m);
if(m == 1)
{
add(i, j + n);
}
}
}
res = 0;
for(int i = 1;i <= n;i ++)
{
memset(vis, false, sizeof(vis));
if(find(i)) res++;
}
if(res >= n) puts("Yes");
else puts("No");
clear();
}
return 0;
}