luogu [ZJOI2007] 矩阵游戏
2024-09-08 16:28:34
[ZJOI2007] 矩阵游戏
题目描述
小 Q 是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 \(n \times n\) 黑白方阵进行(如同国际象棋一般,只是颜色是随意的)。每次可以对该矩阵进行两种操作:
- 行交换操作:选择矩阵的任意两行,交换这两行(即交换对应格子的颜色)。
- 列交换操作:选择矩阵的任意两列,交换这两列(即交换对应格子的颜色)。
游戏的目标,即通过若干次操作,使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
对于某些关卡,小 Q 百思不得其解,以致他开始怀疑这些关卡是不是根本就是无解的!于是小 Q 决定写一个程序来判断这些关卡是否有解。
输入格式
本题单测试点内有多组数据。
第一行包含一个整数 \(T\),表示数据的组数,对于每组数据,输入格式如下:
第一行为一个整数,代表方阵的大小 \(n\)。
接下来 \(n\) 行,每行 \(n\) 个非零即一的整数,代表该方阵。其中 \(0\) 表示白色,\(1\) 表示黑色。
输出格式
对于每组数据,输出一行一个字符串,若关卡有解则输出 Yes
,否则输出 No
。
样例 #1
样例输入 #1
2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0
样例输出 #1
No
Yes
提示
数据规模与约定
- 对于 \(20\%\) 的数据,保证 \(n \leq 7\)。
- 对于 \(50\%\) 的数据,保证 \(n \leq 50\)。
- 对于 \(100\%\) 的数据,保证 \(1 \leq n \leq 200\),\(1 \leq T \leq 20\)。
简析
比赛时的想法是:每行每列只能平行移动,这就说明每一行和每一列必须要有一个方块,
然而只骗了20分
正解居然是二分图匹配!先回想一下二分图匹配的作用:匹配尽量多的边,使其形成一个二分图。二分图就是将所有的点分成两边,是这两部分内部没有边相连。
那这道题为什么是二分图匹配?例如一个点(1, 3)是 1,那他只有到(3, 3)才有用。那就是 1 匹配 3 。只有 n 条边匹配成功才视为形成一条斜线。所列哇 二分图匹配。
#include<iostream>
#include<cstring>
using namespace std;
#define N 520
#define M 100010
int n, m, opt, T;
int h[N], e[M], nxt[M], idx;
int match[N];
bool st[N];
bool find(int x)
{
for(int i = h[x]; i; i = nxt[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
if(!match[j] || find(match[j]))
{
match[j] = x;
return true;
}
}
}
return false;
}
void add(int u, int v)
{
e[++ idx] = v;
nxt[idx] = h[u];
h[u] = idx;
}
int main()
{
cin >> T;
while(T --)
{
idx = 0;
memset(h, 0, sizeof(h));
memset(nxt, 0, sizeof(nxt));
memset(e, 0, sizeof(e));
memset(match, 0, sizeof(match));
cin >> n;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
cin >> opt;
if(opt)
add(i, j);
}
int res = 0;
for(int i = 1; i <= n; i ++)
{
memset(st, false, sizeof(st));
if(find(i))
res ++;
}
if(res == n)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
最新文章
- [C#] 了解过入口函数 Main() 吗?带你用批处理玩转 Main 函数
- 新作《ASP.NET Web API 2框架揭秘》正式出版
- SharePoint Fundation 2013中SecurityTokenServiceApplication错误
- 51Nod 1766 树上的最远点对
- 《C程序设计的抽象思维》2.10编程练习(未完)
- linux端口
- ASP.net 探针
- MFC启动和关闭线程
- MSP430F4152串口操作
- mysql 超时设置
- 欧拉计划 NO05 ps:4题想过,好做,但麻烦,有时间补充,这题也不难!
- C++第五天学习
- pthread创建线程的简单演示
- Java语言的简单基础
- Educational Codeforces Round 60 (Rated for Div. 2)
- Spring学习三
- pdf修复
- C# 生成PDF并下载。
- Activiti6.0 spring5 工作流引擎 java SSM流程审批 项目框架
- 64_n1