BZOJ1059: [ZJOI2007]矩阵游戏(二分图匹配)

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 5954  Solved: 2894

[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

HINT

Source

这题好考智商啊,首先每一行每一列都有$1$是必要条件但不是充要条件

例如:

1 0 0 0

1 0 0 0

0 0 1 0

0 1 0 1

这题的充要条件是:存在$n$个$x,y$互不相同的点

然后把每一个$x$连向能匹配的$y$

来一遍匈牙利即可

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define LL long long 
using namespace std;
const int MAXN = 1e3 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int QwQ, N, cnt = 1;
char s[201];
vector<int> v[MAXN]; 
int link[MAXN], vis[MAXN];
bool Aug(int x) {
    for(int i = 0; i < v[x].size(); i++) {
        int to = v[x][i];
        if(vis[to] == cnt) continue;
        vis[to] = cnt;
        if(!link[to] || Aug(link[to]))
            {link[to] = x; return 1;}
    }
    return 0;
}
main() { 
#ifdef WIN32
   // freopen("a.in", "r", stdin);
    //freopen("b.out", "w", stdout);
#endif
    QwQ = read();
    while(QwQ--) {
        N = read(); cnt = 1;
        for(int i = 1; i <= N; i++) {
            v[i].clear(); link[i] = 0; vis[i] = 0;
            for(int j = 1; j <= N; j++) {
                int opt = read();
                if(opt == 1)
                    v[i].push_back(j);
            }
        }
        int ans = 0;
        for(int i = 1; i <= N; i++, cnt++)
            if(Aug(i))    
                ans++;
        puts(ans == N ? "Yes" : "No");
    }

    return 0;
}   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏木子昭的博客

机器学习三剑客之PandasPandas的两大核心数据结构Panda数据读取(以csv为例)数据处理Pandas的分组和聚合(重要)

Pandas是基于Numpy开发出的,专门用于数据分析的开源Python库 Pandas的两大核心数据结构 Series(一维数据) 允许索引重复...

34860
来自专栏数据结构与算法

2455 繁忙的都市

题目描述 Description        城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的...

40190
来自专栏数据结构与算法

【BZOJ3203】保护出题人(动态规划,斜率优化)

在最优情况下,肯定是存在某只僵尸在到达重点的那一瞬间将其打死 我们现在知道了每只僵尸到达终点的时间,因为僵尸要依次打死。 所以我们假设血量的前缀和是\(s_...

21750
来自专栏逍遥剑客的游戏开发

玻璃效果

14160
来自专栏大数据文摘

动图,用Python追踪NBA球员的运动轨迹

79740
来自专栏hbbliyong

WPF文字修饰——上、中、下划线与基线

       我们知道,文字的修饰包括:空心字、立体字、划线字、阴影字、加粗、倾斜等。这里只说划线字的修饰方式,按划线的位置,我们可将之分为:上划线、中划线、基...

29250
来自专栏数说工作室

【SAS Says】基础篇:基本统计、相关分析与回归分析

特别说明:本节【SAS Says】基础篇:SAS宏初步,用的是数说君学习《The little SAS book》时的中文笔记,我们认为这是打基础的最好选择 S...

51050
来自专栏逍遥剑客的游戏开发

Direct3D学习(四):高级着色语言初探

16770
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程4

教程 OpenGL ES入门教程1-Tutorial01-GLKit OpenGL ES入门教程2-Tutorial02-shader入门 OpenGL E...

36350
来自专栏人人都是极客

GPU渲染之OpenGL的GPU管线

GPU渲染流水线,是硬件真正体现渲染概念的操作过程,也是最终将图元画到2D屏幕上的阶段。GPU管线涵盖了渲染流程的几何阶段和光栅化阶段,但对开发者而言,只有对顶...

21530

扫码关注云+社区

领取腾讯云代金券