题目传送门：【BZOJ 1059】
题目大意：小 Q 很喜欢玩矩阵游戏。矩阵游戏在一个 N * N 黑白方阵进行。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意行列，交换这两列（即交换对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。对于某些关卡，小 Q 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小 Q 决定写一个程序来判断这些关卡是否有解。
输入共 T 组数据。每组数据第一行为一个整数 N，表示一个 N * N 的矩阵；之后输入这个 01 矩阵（0 表示白色，1 表示黑色）。当这组数据有解时，输出 Yes；否则输出 No。
题目分析： （高能！）
（第一次做这道题中……）（结果：WA） 这道题不就是一道贪心水题吗？直接判断每行每列是否全为白色，如果是就直接输出 No，否则输出 Yes 不就行了吗？啊哈哈哈哈哈…… 啊！（被一道从天而降的 WA 闪电击中，倒地不起）
（第二次做这道题中……）（结果：AC） 经历了上次的教训之后，我仔细地看了看这道题，发现：这道题不能这样贪心！每行每列至少有一个黑色只是一项基本条件（必要条件）而已，不能直接判断！例如这组数据：
4 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1我们会发现，无论怎么样调整行列，都无法得到满足条件的答案。 事实上，用贪心来做这道题应该是行不通的，至少我构思了好几种办法，都失败了。
（然后继续 YY 算法中……） ~~（结合着之前做题的经验，我又接着试了试二分图匹配）~~ 能不能这样呢？对于行和列构造出一个二分图，然后，如果当第 i 行第 j 列的数为 1，那么就在二分图对应的地方连一条双向边？那此时又怎么统计并判断答案呢？我惊奇地发现，只要是符合题目条件的答案，它的最大匹配数目都等于 N（换言之，它一定是一个完全匹配）。
那么又该怎么证明呢？这个问题，我还暂时没思考出答案。有兴趣的 OIer 可以自己先看看其他的博客吧 :-) 我一定会在之后补上 233333
下面附上代码：
[cpp] view plain copy print ? #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MX = 205; struct Edge{ int to,next; }; Edge edge[MX * MX * 2]; int n,maps[MX][MX],tots = 0; int head[MX * 5],now = 0,ans = 0,match[MX * 5]; bool vis[MX * 5]; void adde(int u,int v){ edge[++now].to = v; edge[now].next = head[u]; head[u] = now; } bool hungary(int u){ for (int i = head[u];i;i = edge[i].next){ int v = edge[i].to; if (!vis[v]){ vis[v] = true; if (match[v] == 0 || hungary(match[v])){ match[v] = u; return true; } } } return false; } bool check(){ //第一步贪心的预处理 bool row = false,column[MX] = {0}; //这一步可以被省略掉，因为求最大匹配时已经包含了它 for (int i = 1;i <= n;i++){ //实际上，因为它是必要条件 row = false; //所以有了它可以增加严谨性，并不会影响答案 for (int j = 1;j <= n;j++){ //这里可以选择把它注释掉 if (maps[i][j]){ row = true; column[j] = true; } } if (!row){ return false; } } for (int i = 1;i <= n;i++){ if (!column[i]) return false; } return true; } void _init(){ memset(maps,0,sizeof(maps)); memset(head,0,sizeof(head)); memset(edge,0,sizeof(edge)); memset(match,0,sizeof(match)); now = 0,ans = 0,tots = 0; } int main(){ int T; cin>>T; while (T–){ scanf(”%d”,&n); for (int i = 1;i <= n;i++){ for (int j = 1;j <= n;j++){ scanf(”%d”,&maps[i][j]); if (maps[i][j] == 1){ ++tots; adde(i,j + 210); //建立二分图 adde(j + 210,i); } } } for (int i = 1;i <= n;i++){ memset(vis,0,sizeof(vis)); if (hungary(i)) ++ans; } if (tots<n || !check() || ans<n){//1.总共 1 的数量小于 n；2.至少有一行或一列为白色 printf(”No\n”); //3.这个图不是完全匹配 } else { //此时返回 No printf(”Yes\n”); //上述条件都不满足，则返回 Yes } _init(); } return 0; }