二分图

luckydrawbox · 2022-09-21 13:46:44 · 个人记录

二分图与网络流 学习笔记

判定

变量

函数

代码

struct Bipartite_Graph{
    bool is2f;
    int v[N];
    Bipartite_Graph(){
        is2f=1;
        memset(v,0,sizeof(v));
    }
    void dfs(int x,int col){
        if(!is2f)
            return;
        v[x]=col;
        for(int i=G.head[x];i;i=G.nxt[i]){
            int y=G.ver[i];
            if(v[y]==0)
                dfs(y,3-col);
            else if(v[y]==col){
                is2f=0;
                return;
            }
        }
    }
    bool calc(){
        for(int i=1;i<=n;i++)
            if(!v[i]&&is2f)
                dfs(i,1);
        return is2f;
    }
}tu;

最大匹配

变量

函数

代码

struct Bipartite_Graph{
    int v[N];
    int match[N];
    bool dfs(int x,int tag){
        if(v[x]==tag)
            return 0;
        v[x]=tag;
        for(int i=G.head[x];i;i=G.nxt[i]){
            int y=G.ver[i];
            if(!match[y]||dfs(match[y],tag)){
                match[y]=x;
                return 1;
            }
        }
        return 0;
    }
    int ask_max(int n){
        int ans=0;
        memset(v,0,sizeof(v));
        memset(match,0,sizeof(match));
        for(int i=1;i<=n;i++)
            if(dfs(i,i))
                ans++;
        return ans;
    }
}tu;

最大权匹配

变量

函数

代码

struct Bipartite_Graph_Perfect_Matching{
    const long long INF=(1ll<<60);
    int n,pre[N],matcha[N],matchb[N];
    bool va[N],vb[N];
    ll w[N][N],la[N],lb[N],slack[N],delta;
    queue<int>q;
    void init(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                w[i][j]=-INF;
    }
    void bfs(int s){
        memset(va,0,sizeof(va));
        memset(vb,0,sizeof(vb));
        for(int i=1;i<=n;i++)
            slack[i]=INF;
        while(q.size())
            q.pop();
        q.push(s);
        while(1){
            while(q.size()){
                int x=q.front();
                q.pop();
                va[x]=1;
                for(int y=1;y<=n;y++)
                    if(!vb[y])
                        if(la[x]+lb[y]-w[x][y]<slack[y]){
                            slack[y]=la[x]+lb[y]-w[x][y];
                            pre[y]=x;
                            if(!slack[y]){
                                vb[y]=1;
                                if(!matchb[y]){
                                    int z=y;
                                    while(z){
                                        matchb[z]=pre[z];
                                        swap(matcha[pre[z]],z);
                                    }
                                    return;
                                }
                                else
                                    q.push(matchb[y]);
                            }
                        }
            }
            delta=INF;
            for(int i=1;i<=n;i++)
                if(!vb[i])
                    delta=min(delta,slack[i]);
            for(int i=1;i<=n;i++){
                if(va[i])
                    la[i]-=delta;
                if(vb[i])
                    lb[i]+=delta;
                else
                    slack[i]-=delta;
            }
            for(int y=1;y<=n;y++){
                if(!vb[y])
                    if(!slack[y]){
                        vb[y]=1;
                        if(!matchb[y]){
                            int z=y;
                            while(z){
                                matchb[z]=pre[z];
                                swap(matcha[pre[z]],z);
                            }
                            return;
                        }
                        else
                            q.push(matchb[y]);
                    }
            }
        }
    }
    ll km(){
        memset(matcha,0,sizeof(matcha));
        memset(matchb,0,sizeof(matchb));
        for(int i=1;i<=n;i++){
            la[i]=-INF;
            lb[i]=0;
            for(int j=1;j<=n;j++)
                la[i]=max(la[i],w[i][j]);
        }
        for(int i=1;i<=n;i++)
            bfs(i);
        ll ans=0;
        for(int i=1;i<=n;i++)
            ans+=w[matchb[i]][i];
        return ans;
    }
}bg;