KM-最小权完美匹配

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
using namespace std;

const int N =105;
const int M =10005;
const int inf =0x1fffffff;

int n, m, tot, lx[N], ly[N], match[N], h[N], v[M], w[M], nxt[M];
bool visx[N], visy[N];
int lack;

void add(int a, int b, int c)
{
    v[tot] = b;
    w[tot] = c;
    nxt[tot] = h[a];
    h[a] = tot++;
}

bool find(int u)
{
    int i, t;
    visx[u] =true;
    for(i = h[u]; i !=-1; i = nxt[i])
        if(!visy[v[i]])
        {
            t = w[i] - lx[u] - ly[v[i]];
            if(t ==0)
            {
                visy[v[i]] =true;
                if(match[v[i]]==-1|| find(match[v[i]]))
                {
                    match[v[i]] = u;
                    return  true;
                }
            }
            else if(t >0)
                lack = min(lack, t);
        }
    return  false;
}

int calMatch(int n) {
    int ans = 0;
    for(int i =1; i <= n; i++)
    {
        lx[i] = inf;
        ly[i] =0;
        for(int j = h[i]; j !=-1; j = nxt[j])
            lx[i] = min(lx[i], w[j]);
    }
    memset(match, -1, sizeof(match));
    for(int i =1; i <= n; i++)
    {
        memset(visx, false, sizeof(visx));
        memset(visy, false, sizeof(visy));
        lack = inf;
        while(!find(i))
        {
            for(int j =1; j <= n; j++)
            {
                if(visx[j])  lx[j] += lack;
                if(visy[j])  ly[j] -= lack;
            }
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
        }
    }
    ans = 0;
    for(int i =1; i <= n; i++)  ans = ans + lx[i] + ly[i];
    return  ans;
}
}}}

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
using namespace std;
const int N =105;
const int M =10005;
const int inf =0x1fffffff;
int n, m, tot, lx[N], ly[N], match[N], h[N], v[M], w[M], nxt[M];
bool visx[N], visy[N];
int lack;
void add(int a, int b, int c)
{
    v[tot] = b;
    w[tot] = c;
    nxt[tot] = h[a];
    h[a] = tot++;
}
bool find(int u)
{
    int i, t;
    visx[u] =true;
    for(i = h[u]; i !=-1; i = nxt[i])
        if(!visy[v[i]])
        {
            t = w[i] - lx[u] - ly[v[i]];
            if(t ==0)
            {
                visy[v[i]] =true;
                if(match[v[i]]==-1|| find(match[v[i]]))
                {
                    match[v[i]] = u;
                    return  true;
                }
            }
            else if(t >0)
                lack = min(lack, t);
        }
    return  false;
}
int calMatch(int n) {
    int ans = 0;
    for(int i =1; i <= n; i++)
    {
        lx[i] = inf;
        ly[i] =0;
        for(int j = h[i]; j !=-1; j = nxt[j])
            lx[i] = min(lx[i], w[j]);
    }
    memset(match, -1, sizeof(match));
    for(int i =1; i <= n; i++)
    {
        memset(visx, false, sizeof(visx));
        memset(visy, false, sizeof(visy));
        lack = inf;
        while(!find(i))
        {
            for(int j =1; j <= n; j++)
            {
                if(visx[j])  lx[j] += lack;
                if(visy[j])  ly[j] -= lack;
            }
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
        }
    }
    ans = 0;
    for(int i =1; i <= n; i++)  ans = ans + lx[i] + ly[i];
    return  ans;
}