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)即可符合条件。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月31日 星期二 21时54分23秒
4File Name :1059.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23const int N=200*2+7;
24int Link[N];
25bool vis[N];
26vector<int>edge[N];
27int n;
28
29bool Find( int u)
30{
31 int siz = edge[u].size();
32 for ( int i = 0 ; i < siz ; i++)
33 {
34 int v = edge[u][i];
35 if (vis[v]) continue;
36 vis[v] = true;
37 if (Link[v]==-1||Find(Link[v]))
38 {
39 Link[v] = u;
40 return true;
41 }
42 }
43 return false;
44}
45bool hungry( int n)
46{
47 int ret = 0;
48 ms(Link,-1);
49 for ( int i = 1 ; i <= n ; i++)
50 {
51 ms(vis,false);
52 if (Find(i)) ret++;
53 else break;
54 }
55 return ret==n;
56}
57int main()
58{
59 #ifndef ONLINE_JUDGE
60 freopen("./in.txt","r",stdin);
61 #endif
62 int T;
63 cin>>T;
64 while (T--)
65 {
66 cin>>n;
67 for ( int i = 1 ; i <= n ; i++) edge[i].clear();
68 int x;
69 for ( int i = 1 ; i <= n ; i++)
70 {
71 for ( int j = 1 ; j <= n ; j++)
72 {
73 scanf("%d",&x);
74 if (x==1)
75 {
76 edge[i].PB(j);
77 }
78 }
79 }
80 if (hungry(n))
81 puts("Yes");
82 else puts("No");
83 }
84 #ifndef ONLINE_JUDGE
85 fclose(stdin);
86 #endif
87 return 0;
88}