【图论】【二分图匹配】匈牙利与km模板

· · 个人记录

前排提醒

在熟练掌握匈牙利相关算法的dfs写法后，一定要改进为bfs。

km算法bfs写法可以降复杂度n^4为n^3。

后续学习的带花树算法，核心思想只能用bfs实现，使得路径相对确定。（也可能只是我不会dfs写法，欢迎交流）

匈牙利

uoj78

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

inline int read()
{
    int ret=0;char ch=getchar();
    while(ch<'0' || ch>'9')ch=getchar();
    while(ch>='0' && ch<='9')
    {
        ret=ret*10+ch-'0';
        ch=getchar();
    }
    return ret;
}

const int MAXN=510;
int n[2],m,ans;
bool e[MAXN][MAXN];
void input()
{
    n[0]=read();n[1]=read();m=read();
    for(int i=1;i<=m;++i)e[read()][read()]=1;
}

/*命名原则：男生为出点u 女生为入点v*/

int px[MAXN],py[MAXN];//记录匹配 
int pre[MAXN];//记录女生（入点）的前驱 
bool vx[MAXN],vy[MAXN];
queue<int> q;
void aug(int v)
{
    while(v)
    {
        int t=px[pre[v]];
        px[pre[v]]=v;
        py[v]=pre[v];
        v=t;
    }
}
bool bfs(int s)
{
    memset(pre,0,sizeof(pre));//初始化路径 
    memset(vx,0,sizeof(vx));//初始化vis 
    memset(vy,0,sizeof(vy)); 

    while(!q.empty())q.pop();//清空队列 
    q.push(s);

    int u;
    while(!q.empty())
    {
        u=q.front();q.pop();
        vx[u]=1;
        for(int v=1;v<=n[1];++v)if(e[u][v] && !vy[v])
        {
            vy[v]=1;
            pre[v]=u;//记录路径 
            if(!py[v]){aug(v);return 1;}//找到増广路终点
            else q.push(py[v]);//v已有匹配，令u=match[v] 
        }
    }
    return 0;//増广失败 
}

void solve()
{
    for(int i=1;i<=n[0];++i)if(bfs(i))++ans;
}

void output()
{
    printf("%d\n",ans);
    for(int i=1;i<=n[0];++i)printf("%d ",px[i]);
    printf("\n");
}

int main()
{
//  freopen("in.txt","r",stdin);
    input();
    solve();
    output();
    return 0;
}

km

uoj80

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define inf 0x3fffffff
using namespace std;

inline int read()
{
    int ret=0;char ch=getchar();
    while(ch<'0' || ch>'9')ch=getchar();
    while(ch>='0' && ch<='9')
    {
        ret=ret*10+ch-'0';
        ch=getchar();
    }
    return ret;
}

const int MAXN=510;
int n[2],m;
int e[MAXN][MAXN];
void input()
{
    n[0]=read();n[1]=read();m=read();
    if(n[1]<n[0])n[1]=n[0];//添加虚点，保证每个男生都有配偶 
    for(int i=1;i<=m;++i)e[read()][read()]=read();
}

/*命名原则：男生为出点u 女生为入点v*/

int px[MAXN],py[MAXN];//记录匹配 
int lx[MAXN],ly[MAXN];//记录顶标 
int pre[MAXN];//记录女生（入点）的前驱
int slack[MAXN],d;//记录边权与顶标的最小差值，所有slack中的最小值 
bool vx[MAXN],vy[MAXN];
queue<int> q;
void aug(int v)
{
    int t;
    while(v)
    {
        t=px[pre[v]];
        px[pre[v]]=v;
        py[v]=pre[v];
        v=t;
    }
}
void bfs(int s)
{
    fill(slack+1,slack+n[1]+1,inf);
    memset(pre,0,sizeof(pre));
    memset(vx,0,sizeof(vx));
    memset(vy,0,sizeof(vy));

    while(!q.empty())q.pop();
    q.push(s);

    int u;
    while(1)
    {
        while(!q.empty())
        {
            u=q.front();q.pop();
            vx[u]=1;
            for(int v=1;v<=n[1];++v)if(!vy[v])//枚举可増广v 
            {
                if(lx[u]+ly[v]-e[u][v]<slack[v])//増广路径选择slack最小的 
                {
                    slack[v]=lx[u]+ly[v]-e[u][v];
                    pre[v]=u;//记录v的前驱 

                    if(!slack[v])//边在相等子图中，可以増广 
                    {
                        vy[v]=1;
                        if(!py[v]){aug(v);return;}//找到増广路终点 
                        else q.push(py[v]);//v已有匹配，令v=py[v] 
                    } 
                }
            }
        }
        //増广失败，扩大子图 
        d=inf;
        for(int i=1;i<=n[1];++i)if(!vy[i])d=min(d,slack[i]);//寻找所有差值中最小的
        if(d==inf)break;//扩大失败 
        //修改顶标 
        for(int i=1;i<=n[0];++i)if(vx[i])lx[i]-=d;
        for(int i=1;i<=n[1];++i)if(vy[i])ly[i]+=d;else slack[i]-=d;
        //将新可増广点入队，为下次増广作准备
        for(int i=1;i<=n[1];++i)if(!vy[i] && !slack[i])
        {
            vy[i]=1;
            if(!py[i]){aug(i);return;}//找到増广路终点 
            else q.push(py[i]);//v已有匹配，令v=py[v] 
        } 
    }
}

void km()
{
    for(int u=1;u<=n[0];++u)
        for(int v=1;v<=n[1];++v)
            lx[u]=max(lx[u],e[u][v]);//初始化lx 
    for(int i=1;i<=n[0];++i)bfs(i);
}

void output()
{
    ll ans=0;
    for(int i=1;i<=n[0];++i)ans+=lx[i];
    for(int i=1;i<=n[1];++i)ans+=ly[i];
    printf("%lld\n",ans);

    for(int i=1;i<=n[0];++i)if(e[i][px[i]])printf("%d ",px[i]);else printf("0 ");
    printf("\n");
}

int main()
{
//  freopen("in.txt","r",stdin);
    input();
    km();
    output();
    return 0;
}