[LuoguP3386] 二分图匹配

分析

网络流算法,左部右部分别连源点汇点,置容量为 1,跑一遍 dinic 或者 EK 即可

代码

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e3+3,M=1e5+3,INF=0x3f3f3f3f;
int n,m,k,s,t,max_flow;

struct qxx{int nex,t,v;};
qxx e[M*2];
int h[N],cnt=1;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
void add_flow(int f,int t,int v){add_path(f,t,v);add_path(t,f,0);}

int rk[N];
bool bfs(){memset(rk,0,sizeof(rk));
    queue<int> q;
    q.push(s),rk[s]=1;
    while(q.size()){int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
            if(w&&!rk[v])rk[v]=rk[u]+1,q.push(v);
        }
    }
    return rk[t];
}
int dinic(int u,int flow){if(u==t)return flow;
    int rest=flow,x;
    for(int i=h[u];i&&rest;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
        if(!w||rk[v]!=rk[u]+1)continue;
        x=dinic(v,min(rest,w));
        if(x)e[i].v-=x,e[i^1].v+=x,rest-=x;
        else rk[v]=0;
    }
    return flow-rest;
}
int main(){scanf("%d%d%d",&n,&m,&k);
    for(int u,v,i=1;i<=k;i++){scanf("%d%d",&u,&v);
        if(u>n||v>m)continue;
        add_flow(u,v+n,1);
    }
    s=0,t=n+m+1;
    for(int i=1;i<=n;i++)add_flow(s,i,1);
    for(int i=1;i<=m;i++)add_flow(i+n,t,1);
    while(bfs())for(int i=dinic(s,INF);i;i=dinic(s,INF))max_flow+=i;
    printf("%d",max_flow);
    return 0;
}

 上一篇
[LuoguP2756] 飞行员配对方案问题 [LuoguP2756] 飞行员配对方案问题
分析二分图匹配,直接网络流模板 输出方案的时候,判断每条边是否图上剩余容量为 0 的边即可 代码#include<cstdio> #include<cstring> #include<queue> using namesp
2018.12.21
下一篇 
二分小结 二分小结
二分概述二分不同于分治,它根据问题的单调维度求解的特点,在该维度上折半查找答案,使复杂度系数由 降低到 . [TJOI2007] 路标设置求最大距离的最小值,典型的二分答案 #include<bit
2018.12.19
  目录