1059: [ZJOI2007]矩阵游戏
Description
小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N
*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择
矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意行列，交换这两列（即交换
对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑
色。对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小Q决定写一个程
序来判断这些关卡是否有解。
Input
第一行包含一个整数T，表示数据的组数。接下来包含T组数据，每组数据第一行为一个整数N，表示方阵的大
小；接下来N行为一个N*N的01矩阵（0表示白色，1表示黑色）。
Output
输出文件应包含T行。对于每一组数据，如果该关卡有解，输出一行Yes；否则输出一行No。
Sample Input
2 2 0 0 0 1 3 0 0 1 0 1 0 1 0 0
Sample Output
No Yes 【数据规模】 对于100%的数据，N ≤ 200
其实这道还蛮简单的……我这么弱都做出来了QAQ来着弱者的哀叹。
手玩了一下一些数据，发现一旦钦定了某一点移到指定位置，那么此点同行同列的点对于答案就没有贡献了。
（由于无论怎么变换，在同一列同一行的点始终在同一列同一行，而题目要求的是在对角线上，显然其他点对答案没有贡献了QAQ）
所以问题就转换为了在图中能不能找到n个不同行不同列的点。
以横坐标为左边的点，纵坐标为右边的点，就是二分图啦ww
如果不是所有点都有匹配的话就是No了w反则是Yes。
辣鸡代码如下qwq
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 #include<
string>
6 #include<cmath>
7 #include<algorithm>
8 #include<queue>
9 #include<vector>
10 using namespace std;
11 int t,n;
12 int mp[
205][
205],cx[
205],cy[
205],vis[
205];
13 int find(
int x)
14 {
15 for (
int i=
1;i<=n;i++
)
16 {
17 if (mp[x][i]&&!
vis[i])
18 {
19 vis[i]=
1;
20 if (!cy[i]||
find(cy[i]))
21 {
22 cy[i]=
x;
23 return 1;
24 }
25 }
26 }
27 return 0;
28 }
29 int main()
30 {
31 scanf(
"%d",&
t);
32 for (
int cs=
1;cs<=t;cs++
)
33 {
34 memset(mp,
0,
sizeof(mp));
35 memset(cx,
0,
sizeof(cx));
36 memset(cy,
0,
sizeof(cy));
37 scanf(
"%d",&
n);
38 for (
int i=
1;i<=n;i++
)
39 {
40 for (
int j=
1;j<=n;j++
)
41 {
42 int x;
43 scanf(
"%d",&
x);
44 if (x) mp[i][j]=
1;
45 }
46 }
47 int f=
0;
48 for (
int i=
1;i<=n;i++
)
49 {
50 if (!
cx[i])
51 {
52 memset(vis,
0,
sizeof(vis));
53 if (!
find(i))
54 {
55 f=
1;
56 printf(
"No\n");
57 break;
58 }
59 }
60 }
61 if (!f) printf(
"Yes\n");
62 }
63 return 0;
64 }
转载于:https://www.cnblogs.com/zengziyun/p/6399060.html
相关资源：各显卡算力对照表！
