巴黎公社社员造船厂Project1129研制成功-白红宇

巴黎公社社员造船厂Project1129研制成功

阅读量：4635 次

发布时间：2019-06-09

本文共 3815 字，大约阅读时间需要 12 分钟。

这道题神啊.

看了一下午没有思路,感觉是二分图没有深刻理解,又重新看了一遍蓝书上的二分图,还打了道题练手,然而还是没有想出这道题......

于是恰饭回来决定看下题解,恍然大悟.

同志们可以把每一个点看做一条匹配边,把它的的行数和列数连一条边,会发现整幅图是一组匹配.

在交换行和列的时候,相当于在匈牙利算法中进行协商的过程,所以对最大匹配不变.

如果交换后可以有n个及以上的匹配,就说明一定可以实现题意.

配图如下(图里的字体有点小请见谅):

配图1.png

配图2.png

然后就是跑一个裸的匈牙利,求出匹配个数就可以了.

代码:

#pragma GCC diagnostic error "-std=c++11"#pragma GCC target("sse2")#pragma GCC optimize(3)#pragma GCC target("avx")#pragma GCC optimize("Ofast")#pragma GCC optimize("inline")#pragma GCC optimize("-fgcse")#pragma GCC optimize("-fgcse-lm")#pragma GCC optimize("-fipa-sra")#pragma GCC optimize("-ftree-pre")#pragma GCC optimize("-ftree-vrp")#pragma GCC optimize("-fpeephole2")#pragma GCC optimize("-ffast-math")#pragma GCC optimize("-fsched-spec")#pragma GCC optimize("unroll-loops")#pragma GCC optimize("-falign-jumps")#pragma GCC optimize("-falign-loops")#pragma GCC optimize("-falign-labels")#pragma GCC optimize("-fdevirtualize")#pragma GCC optimize("-fcaller-saves")#pragma GCC optimize("-fcrossjumping")#pragma GCC optimize("-fthread-jumps")#pragma GCC optimize("-funroll-loops")#pragma GCC optimize("-fwhole-program")#pragma GCC optimize("-freorder-blocks")#pragma GCC optimize("-fschedule-insns")#pragma GCC optimize("inline-functions")#pragma GCC optimize("-ftree-tail-merge")#pragma GCC optimize("-fschedule-insns2")#pragma GCC optimize("-fstrict-aliasing")#pragma GCC optimize("-fstrict-overflow")#pragma GCC optimize("-falign-functions")#pragma GCC optimize("-fcse-skip-blocks")#pragma GCC optimize("-fcse-follow-jumps")#pragma GCC optimize("-fsched-interblock")#pragma GCC optimize("-fpartial-inlining")#pragma GCC optimize("no-stack-protector")#pragma GCC optimize("-freorder-functions")#pragma GCC optimize("-findirect-inlining")#pragma GCC optimize("-fhoist-adjacent-loads")#pragma GCC optimize("-frerun-cse-after-loop")#pragma GCC optimize("inline-small-functions")#pragma GCC optimize("-finline-small-functions")#pragma GCC optimize("-ftree-switch-conversion")#pragma GCC optimize("-foptimize-sibling-calls")#pragma GCC optimize("-fexpensive-optimizations")#pragma GCC optimize("-funsafe-loop-optimizations")#pragma GCC optimize("inline-functions-called-once")#pragma GCC optimize("-fdelete-null-pointer-checks")#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;struct edge{    int to,next;}e[1000010];int t,n,size,CommunismParty_cnt;int head[1000010],match[1000010];bool flag[1000010];inline void EdgeAdd(int,int);inline void Hungary();inline bool find(int);int main(){    scanf("%d",&t);    for(int _=1;_<=t;_++)    {        scanf("%d",&n);        CommunismParty_cnt=0;        size=0;        memset(head,-1,sizeof(head));        memset(match,0,sizeof(match));        memset(e,0,sizeof(e));        for(int __=1;__<=n;__++)        {            for(int ___=1;___<=n;___++)            {                int CommunistYouthLeague_color;                scanf("%d",&CommunistYouthLeague_color);                if(CommunistYouthLeague_color==1)                {                    EdgeAdd(__,___);                }            }        }        Hungary();        printf("%s\n",CommunismParty_cnt>=n?"Yes":"No");    }return 0;}inline void EdgeAdd(int from,int to){    e[++size].to=to;    e[size].next=head[from];    head[from]=size;}inline void Hungary(){    for(int _=1;_<=n;_++)    {        memset(flag,false,sizeof(flag));        if(find(_)==true)        {            CommunismParty_cnt++;        }    }}inline bool find(int from){    for(int _=head[from];_!=-1;_=e[_].next)    {        int to=e[_].to;        if(flag[to]==false)        {            flag[to]=true;            if(match[to]==0||find(match[to])==true)            {                match[to]=from;                return true;            }        }    }return false;}