M_sea

洛谷1129 [ZJOI2007]矩阵游戏
Luogu算法考虑行与列匹配。对于每一个黑格,从行向列连边即可。然后跑匈牙利,若匹配数为$n$,则有解,否则无解。...
扫描右侧二维码阅读全文
20
2018/08

洛谷1129 [ZJOI2007]矩阵游戏

Luogu

算法

考虑行与列匹配。

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

然后跑匈牙利,若匹配数为$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 年 12 月 01 日 08 : 16 PM

发表评论