P1129 [ZJOI2007]矩阵游戏二分图匹配

骑猪看日落 2021-11-17 15:30 246阅读 0赞

思路：脑子+二分图匹配

提交：1次（课上讲过）

题解：

发现：如果符合题意，那么行和列一定是一一匹配的（必要条件），所以最大匹配必须是$n$。

同时我们发现，一定可以通过交换行列的方式，将（看起来）有交错的最大匹配，转换成符合题意的状态。

所以最大匹配是$n$即为判断依据。

![1599173-20190718204619766-395818687.png][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #define R register int
    using namespace std;
    #define ull unsigned long long
    #define ll long long
    #define pause (for(R i=1;i<=10000000000;++i))
    #define IN freopen("NOIPAK++.in","r",stdin)
    #define OUT freopen("out.out","w",stdout)
    namespace Fread {
        static char B[1<<15],*S=B,*D=B;
    #ifndef JACK
        #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
    #endif
        inline int g() {
            R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
            do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
        } inline bool isempty(const char& ch) {
        return ch<=36||ch>=127;}
        inline void gs(char* s) {register char ch; while(isempty(ch=getchar())); do *s++=ch; while(!isempty(ch=getchar()));}
    }using Fread::g; using Fread::gs;
    const int N=210;
    int vis[N],pre[N],t,ans,n,tim; 
    bool e[N][N];
    inline bool dfs(int u) {
        for(R v=1;v<=n;++v) if(e[u][v]&&vis[v]!=tim) {
            vis[v]=tim; if(!pre[v]||dfs(pre[v])) {pre[v]=u; return true ;}
        } return false;
    }
    signed main() {
    #ifdef JACK
    #endif
        t=g(); while(t--) { ans=0,tim=0;
            memset(vis,0,sizeof(vis)),memset(pre,0,sizeof(pre)),memset(e,false,sizeof(e));
            n=g(); for(R i=1;i<=n;++i) for(R j=1;j<=n;++j) e[i][j]=g();
            for(R i=1;i<=n;++i) ++tim,ans+=dfs(i);
            if(ans==n) printf("Yes\n");
            else printf("No\n");
        }
    }

--------------------

2019.07.18

转载于:https://www.cnblogs.com/Jackpei/p/11209915.html

[1599173-20190718204619766-395818687.png]: /images/20211116/a9432f656f614333925c0f5c569d82f6.png