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

Posted by 111qqz on Tuesday, October 31, 2017

TOC

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;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付