M_sea

洛谷1129 [ZJOI2007]矩阵游戏
题目描述小$Q$是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个$N ...
扫描右侧二维码阅读全文
20
2018/08

洛谷1129 [ZJOI2007]矩阵游戏

题目描述

小$Q$是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个$N \times N$黑白方阵进行(如同国际象棋一般,只是颜色是随意的)。每次可以对该矩阵进行两种操作:

行交换操作:选择矩阵的任意两行,交换这两行(即交换对应格子的颜色)

列交换操作:选择矩阵的任意两列,交换这两列(即交换对应格子的颜色)

游戏的目标,即通过若干次操作,使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。

对于某些关卡,小$Q$百思不得其解,以致他开始怀疑这些关卡是不是根本就是无解的!于是小$Q$决定写一个程序来判断这些关卡是否有解。

传送门

算法

考虑行与列匹配。

对于每一个黑格,从行向列连边即可。

然后跑匈牙利,若匹配数为$n$,则有解,否则无解。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge { int v,nxt; };
Edge e[40010];
int head[210],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int link[210];
bool vis[210];

inline bool Hungary(int u) {
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!vis[v]) {
            vis[v]=1;
            if (!link[v]||Hungary(link[v])) {
                link[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    int T=read();
    while (T--) {
        cnt=0;
        memset(head,0,sizeof(head));
        memset(link,0,sizeof(link));
        
        int n=read();
        for (re int i=1;i<=n;i++)
            for (re int j=1;j<=n;j++) {
                int k=read();
                if (k) addEdge(i,j);
            }
        
        int ans=0;
        for (re int i=1;i<=n;i++) {
            memset(vis,0,sizeof(vis));
            if (Hungary(i)) ans++;
        }
        
        if (ans==n) puts("Yes");
        else puts("No");
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 15 PM

发表评论