Luogu P1407 [国家集训队]稳定婚姻（二分图写法）-白红宇

Luogu P1407 [国家集训队]稳定婚姻（二分图写法）

阅读量：5214 次

发布时间：2019-06-14

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

RT，这是一道强联通分量。

而我一个热爱匈牙利的OIer

默默敲下了...

#include
    
     #include
     
      #include
      
       #include
       
        #include
        using namespace std;int n,m,cnt,vis[100005],match[100005],head[100005],now[100005];map
         
           boy,girl;struct edge{ int u,v,next;bool dis;}e[100005];inline void add(int u,int v){ e[++cnt].v=v; e[cnt].u=u; e[cnt].next=head[u]; head[u]=cnt;}inline bool dfs(int u){ for(int i=head[u];i!=-1;i=e[i].next){ if(e[i].dis)continue; int v=e[i].v; if(!vis[v]){ vis[v]=1; if(match[v]==-1||dfs(match[v])){ match[v]=u; return 1; } } } return 0;}int main(){ memset(match,-1,sizeof(match)); memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1;i<=n;i++){ string s,t; cin>>s>>t; boy[s]=i; girl[t]=i; add(boy[s],girl[t]); now[i]=cnt; } scanf("%d",&m); for(int i=1;i<=m;i++){ string s,t; cin>>s>>t; add(boy[s],girl[t]); } for(int i=1;i<=n;i++){ memset(match,-1,sizeof(match)); int tot=0; e[now[i]].dis=1; for(int j=1;j<=n;j++){ memset(vis,0,sizeof(vis)); tot+=dfs(j); } if(tot==n){ printf("Unsafe\n"); } else{ printf("Safe\n"); } e[now[i]].dis=0; }}

然后各种常数优化

NM的register，hash，读入优化

P用么得

然后去翻了洛谷题解

大概基本上都是强联通分量的

但是二分图

然后重拾了信心QwQ

但是那位巨佬的二分图建图是把汉字和妹子统一编号的，我不习惯那样

所以抄不了题解，只好自己刚

心态崩盘后仔细研读了那位巨佬的题解

发现根！本！不！是！一般的二分图写法

因为一开始是匹配好的

用我的码风来描述就是：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        using namespace std;int n,m,cnt,vis[100005],match[100005],head[100005],dis;map
         
           boy,girl;struct edge{ int u,v,next;}e[100005];inline void add(int u,int v){ e[++cnt].v=v; e[cnt].u=u; e[cnt].next=head[u]; head[u]=cnt;}inline bool dfs(int u){ for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; if(u==dis&&v==dis)continue; if(!vis[v]){ vis[v]=1; if(match[v]==-1||dfs(match[v])){ return 1; } } } return 0;}int main(){ memset(match,-1,sizeof(match)); memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1;i<=n;i++){ string s,t; cin>>s>>t; boy[s]=i; girl[t]=i; match[i]=i; } scanf("%d",&m); for(int i=1;i<=m;i++){ string s,t; cin>>s>>t; add(boy[s],girl[t]); } for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); match[i]=-1; dis=i; if(dfs(i)){ printf("Unsafe\n"); } else{ printf("Safe\n"); } match[i]=i; }}