跳转至

二分图相关

二分图最大匹配

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
namespace Hungrian
{
    int N,match[MAX],vis[MAX],tot;
    vector<int> G[MAX];
    bool dfs(int now,int id)
    {
        for(auto to:G[now]) if(vis[to]!=id)
        {
            vis[to]=id;
            if(!match[to]||dfs(match[to],id)) return match[to]=now,1;
        }
        return 0;
    }
    inline void Work() {for(int i=1;i<=N;++i) tot+=dfs(i,i);}
}

二分图带权最大完美匹配

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
namespace KM
{
    constexpr int Na=510;
    int N,res,p,q,id,val,d[Na][Na];
    int vis[Na],match[Na],pre[Na],slack[Na],lx[Na],ly[Na];
    inline void Augment(int s)
    {
        match[0]=s,p=q=id=val=0;
        fill(pre+1,pre+N+1,0),fill(slack+1,slack+N+1,INF),fill(vis+1,vis+N+1,0);
        while(match[q])
        {
            p=match[q=id],vis[q]=1,val=INF;
            for(int i=1;i<=N;++i) if(!vis[i])
            {
                if(slack[i]>lx[p]+ly[i]-d[p][i]) slack[i]=lx[p]+ly[i]-d[p][i],pre[i]=q;
                if(slack[i]<val) val=slack[id=i];
            }
            for(int i=0;i<=N;++i) if(vis[i]) lx[match[i]]-=val,ly[i]+=val; else slack[i]-=val;
        }
        for(;q;q=pre[q]) match[q]=match[pre[q]];
    }
    inline void Work()
    {
        for(int i=1;i<=N;++i)
        {
            lx[i]=-INF,ly[i]=0;
            for(int j=1;j<=N;++j) cmax(lx[i],d[i][j]);
        }
        for(int i=1;i<=N;++i) Augment(i);
        for(int i=1;i<=N;++i) res+=lx[i]+ly[i];
    }
}