bzoj 1059: [ZJOI2007]矩阵游戏 (匈牙利算法)

Oct 31, 2017 · 2 min read · 匈牙利算法

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
************************************************ */

#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=200*2+7;
int Link[N];
bool vis[N];
vector<int>edge[N];
int n;

bool Find( int u)
{
    int siz = edge[u].size();
    for ( int i = 0 ; i < siz ; i++)
    {
    int v = edge[u][i];
    if (vis[v]) continue;
    vis[v] = true;
    if (Link[v]==-1||Find(Link[v]))
    {
        Link[v] = u;
        return true;
    }
    }
    return false;
}
bool hungry( int n)
{
    int ret = 0;
    ms(Link,-1);
    for ( int i = 1 ; i <= n ; i++)
    {
    ms(vis,false);
    if (Find(i)) ret++;
    else break;
    }
    return ret==n;
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("./in.txt","r",stdin);
  #endif
    int T;
    cin>>T;
    while (T--)
    {
        cin>>n;
        for ( int i = 1 ; i <= n ; i++) edge[i].clear();
        int x;
        for ( int i = 1 ; i <= n ; i++)
        {
        for ( int j = 1 ; j <= n ; j++)
        {
            scanf("%d",&x);
            if (x==1)
            {
            edge[i].PB(j);
            }
        }
        }
        if (hungry(n))
        puts("Yes");
        else puts("No");
    }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}