bzoj 1059: [ZJOI2007]矩阵游戏 (匈牙利算法)
1059: [ZJOI2007]矩阵游戏
Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5251 Solved: 2512 [Submit][Status][Discuss]
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
思路：
纠结了一下建图，由于每个黑点可以按照行换，也可以按照列换。所以我建了一个1..n到1..2n的二分图做匹配。
左边集合是n个对角线上的点，右边集合是行号+列号。
但是每次匹配的时候，一个对角线上的点会同时消耗到匹配的行号和列号。。感觉不是很对啊。。。
实际上发现，我们只需要建立一个n到n的二分图就行了。
原因是，如果有解，那么只需要行或者列的一种变换，就可以达到规定的图案。
比如现在(2,5)是1,（2,2)和(5,5)是0，我们只需要连一条边表示(2,5)可以换到(2,2)即可，不需要连表示(2,5)可以换到(5,5)的边
原因是，如果(2,5)换到(5,5)，那么(2,2)也跟着换到了(5,2)，我们不考虑之前的(2,2)是什么，被换之后的(2,2)必须是1才符合题意，也就是换之前的(5,2)必须是1.
既然(5,2)是1，那么从(5,2)换到(5,5)即可符合条件。
/* ***********************************************
Author :111qqz
Created Time :2017年10月31日 星期二 21时54分23秒
File Name :1059.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=200*2+7;
7int Link[N];
8bool vis[N];
9vector<int>edge[N];
10int n;
1bool Find( int u)
2{
3 int siz = edge[u].size();
4 for ( int i = 0 ; i < siz ; i++)
5 {
6 int v = edge[u][i];
7 if (vis[v]) continue;
8 vis[v] = true;
9 if (Link[v]==-1||Find(Link[v]))
10 {
11 Link[v] = u;
12 return true;
13 }
14 }
15 return false;
16}
17bool hungry( int n)
18{
19 int ret = 0;
20 ms(Link,-1);
21 for ( int i = 1 ; i <= n ; i++)
22 {
23 ms(vis,false);
24 if (Find(i)) ret++;
25 else break;
26 }
27 return ret==n;
28}
29int main()
30{
31 #ifndef ONLINE_JUDGE
32 freopen("./in.txt","r",stdin);
33 #endif
34 int T;
35 cin>>T;
36 while (T--)
37 {
38 cin>>n;
39 for ( int i = 1 ; i <= n ; i++) edge[i].clear();
40 int x;
41 for ( int i = 1 ; i <= n ; i++)
42 {
43 for ( int j = 1 ; j <= n ; j++)
44 {
45 scanf("%d",&x);
46 if (x==1)
47 {
48 edge[i].PB(j);
49 }
50 }
51 }
52 if (hungry(n))
53 puts("Yes");
54 else puts("No");
55 }
56 #ifndef ONLINE_JUDGE
57 fclose(stdin);
58 #endif
59 return 0;
60}