正文

矩阵游戏|zjoi2007|bzoj1059|codevs1433|luogup1129|二分图匹配|匈牙利算法|elena

AlenaNuna  AlenaNuna  2022-09-17  597

关键词：

1059: [ZJOI2007]矩阵游戏

Time Limit: 10 Sec Memory Limit: 162 MB

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

思路：这个题目表面上看叫人丝毫没有丝绸之路qwq可是网络流啊匈牙利算法啥的题目写多了被套路多了之后就会变得熟练_(:з」∠)_

题目中给我们的操作是可以交换任意两行和任意两列，我们可以确定同一行的两个格子永远在同一行，同一列的也是一样，同一行的两个格子永远不会跑到不同的两行里去，所以两个格子我们只能取一个来用，另外一个是没有作用的，不存在把这个格子放在这个对角线的一个地方，另一个格子放在对角线上的另一个地方。因为对角线上的格子横纵坐标都是不相同的。

题目中要求的形状是正对角线也就是从左上角到右下角的连线。我们可以把每一个1格子的横坐标和纵坐标连边，然后匈牙利算法找出二分图最大匹配，如果最大匹配数等于n，则答案是yes，反之则是no。

为什么最大匹配数为n就是yes呢？因为我们可以这么想：假设有一个3*3的矩阵，从左上角到右下角的连线经过的格子依次是（1,1），（2,2）和（3,3）这3个格子。假如这时候（1,2）也有一个1号格子，照我们前面的说法，把这些格子的横纵坐标依次连边。然后照二分图匹配的思想，如果（1，2）配对成功的话，就只能配对成（1,2）和（3,3）这两对了，也只取了这两个格子，无法组成连线，是不符合条件的，所以（1,2）不能配对，我们应该找最大匹配。

因为当最大匹配数等于n时，就说明正好有n个格子的横纵坐标是匹配的，这些格子的横纵坐标不会相同，就会组成一条线，我们可以把交换行列看成改变格子的位置，所以如果组成的是左下角到右上角的线，可以通过交换列来达到理想位置。那条线符合答案要求。因为我们可以通过换行换列来使格子到达该到的地方。可以通过交换行列来改变格子的位置，但是同行列的格子间会受到影响，所以只有不同行列的格子改变到理想的位置后不会影响到其他的格子。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib> 
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 int read()
 8 {
 9     int x=0,f=1; char c=getchar();
10     while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1; c=getchar();}
11     while (c>=‘0‘&&c<=‘9‘) {x=x*10+c-‘0‘;c=getchar();}
12     return x*f;
13 }
14 int num_edge,head[500],T,sum,n,match[500];
15 bool book[500];
16 struct Edge
17 {
18     int next;
19     int to;
20 }edge[81000];
21 void add_edge(int from,int to)
22 {
23     edge[++num_edge].next=head[from];
24     edge[num_edge].to=to;
25     head[from]=num_edge;
26 }
27 bool dfs(int u)
28 {
29     for (int i=head[u]; i; i=edge[i].next)
30         if (book[edge[i].to]==0) {
31             book[edge[i].to]=1;
32             if (match[edge[i].to]==0||dfs(match[edge[i].to])) {
33                 match[edge[i].to]=u;
34                 match[u]=edge[i].to;
35                 return 1;
36             }
37         }
38     return 0;
39 }
40 int main()
41 {
42     T=read();
43     while (T--) {
44         bool p=1;
45         sum=0;
46         num_edge=0;
47         n=read();
48         memset(match,0,sizeof(match));
49         memset(head,0,sizeof(head));
50         for (int i=1; i<=n; i++)
51             for (int j=1; j<=n; j++) {
52                 int x=read();
53                 if (x==1) {
54                     add_edge(i,j+n);
55                     add_edge(j+n,i);
56                 }
57             }
58         for (int i=1; i<=n; i++) {
59             memset(book,0,sizeof(book));
60             book[i]=1;
61             if (!dfs(i)) {
62                 p=0;
63                 break;
64             }
65         }
66         if (p) puts("Yes"); else puts("No");
67     }
68     return 0;
69 }

矩阵游戏

注意：每一组数据开始时都要清空边表的num_edge和head数组。

注意：检查代码时就算是定义部分也要检查，别自以为是。

有问题可以直接在评论里面提问，有需要转载的请得到我的允许，否则按侵权处理。

Elena loves NiroBC forever!

bzoj1059:[zjoi2007]矩阵游戏

1059:[ZJOI2007]矩阵游戏TimeLimit:10Sec MemoryLimit:162MBSubmit:5223 Solved:2503[Submit][Status][Discuss]Description　　小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵... 查看详情

bzoj1059[zjoi2007]矩阵游戏二分图匹配

1059:[ZJOI2007]矩阵游戏TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 5452 Solved: 2629[Submit][Status][Discuss]Description　　小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏— 查看详情

bzoj1059[zjoi2007]矩阵游戏(二分图最大匹配)

1059:[ZJOI2007]矩阵游戏TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 5281 Solved: 2530[Submit][Status][Discuss]Description　　小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。查看详情

bzoj-1059:[zjoi2007]矩阵游戏(二分图最大匹配)

1059:[ZJOI2007]矩阵游戏TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 5245 Solved: 2511[Submit][Status][Discuss]Description　　小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一查看详情

bzoj1059zjoi2007—矩阵游戏

...com/JudgeOnline/problem.php?id=1059 (题目链接)题意　　一个01矩阵，可以任意交换两行或两列，问能否经过若干次交换后使主对角线全为1。Solution　　hzwer：同行同列的点无论经过多少次变换仍然同行或同列，所以题目可转换为能不... 查看详情

bzoj1059:[zjoi2007]矩阵游戏

...子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行... 查看详情

[bzoj]1059矩阵游戏(zjoi2007)

...了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行... 查看详情

bzoj1059:[zjoi2007]矩阵游戏

bzoj1059：[zjoi2007]矩阵游戏——题解(代码片段)

...子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意查看详情

bzoj1059[zjoi2007]矩阵游戏

题解：二分图匹配行列建点每一条边i->j表示第i行移动到第j行符合题意，即a[i][j]=1可证明不需考虑列的交换求最大匹配即可#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<queue>usingnamespacestd;con 查看详情

_bzoj1059[zjoi2007]矩阵游戏二分图匹配

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1059保存匈牙利模板。#include<cstdio>#include<cstring>constintmaxn=205;constchar_outp[2][5]={"No","Yes"};intT,n,left[maxn],ans;charg[maxn][maxn], 查看详情

bzoj1059zjoi2007矩阵游戏

一开始还以为是DP什么的，但是瞄了眼讨论区发现好像可以建模成二分图匹配。于是乎瞎造了几组数据手动模拟了下，发现只要最后匹配数量>=n就有解。Orz还是自己太弱，不能一眼看出算法去建模。话说这道题目和ZJOI2009那道... 查看详情

bzoj1059:[zjoi2007]矩阵游戏(二分图匹配)(代码片段)

1059:[ZJOI2007]矩阵游戏题目：传送门题解：　　为了赶上苏大佬的光速的脚步...刷了题水题，不过苏大佬好像一早就搞定了，所以也没有什么关系了对吧！　　其实说水题的话还不能完全算是，但如果要是发散一下思维很容易... 查看详情

bzoj1059[zjoi2007]矩阵游戏：二分图匹配

...ydsy.com/JudgeOnline/problem.php?id=1059题意：　　给你一个n*n的01矩阵。　　你可以任意次地交换某两行或某两列。　　问你是否可以让这个矩阵的主对角线(左上角到右下角的连线)上的格子均为黑色。题解：　　可以发现，对于一... 查看详情

[bzoj1059][zjoi2007]矩阵游戏(二分图匹配)

bzoj1059:[zjoi2007]矩阵游戏[二分图][二分图最大匹配]

洛谷p1129bzoj1059cogs660[zjoi2007]矩阵游戏

...子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行... 查看详情

矩阵游戏|zjoi2007|bzoj1059|codevs1433|luogup1129|二分图匹配|匈牙利算法|elena

1059:[ZJOI2007]矩阵游戏TimeLimit: 10Sec MemoryLimit: 162MBDescription　　小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是... 查看详情