二分图的最优匹配模版

时间：2021-08-07 05:53:02

二分图的的最优匹配是在求二分图的完备匹配的基础之上求出的， 通过不断的扩展完备匹配，最终达到相等子图。而相等子图的完备匹配就是最优匹配。在此定义了可行顶标。

一个关于最优匹配讲的很好的博客地址：http://www.cnblogs.com/one--world--one--dream/archive/2011/08/14/2138385.html

hdu2255

最大权最优匹配模版：

顶标lx【i】表示与顶点i相连的所有边的最大值； 顶标ly【j】为零（为了保证lx【i】+ly【j】>=w【i】【j】）

当不存在完备匹配时，进行扩展时，顶标lx减去扩展量， 顶标ly加上扩展量

时间复杂度为0（n^4）

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 1000 + 10;
int Map[maxn][maxn], n;
int Ls[maxn], Lt[maxn], p[maxn];
bool vs[maxn], vt[maxn];
bool dfs(int u)
{
    vs[u] = true;
    for(int v = 1; v <= n; v++)
    {
        if(Ls[u]+Lt[v]==Map[u][v] && !vt[v])
        {
            vt[v] = true;
            if(p[v]==-1 || dfs(p[v]))
            {
                p[v] = u;
                return true;
            }
        }
    }
    return false;
}
void update()
{
    int a = 1<<30;
    for(int i = 1; i <= n; i++)
        if(vs[i])
            for(int j = 1; j <= n; j++)
                if(!vt[j])
                    a = min(a, Ls[i]+Lt[j]-Map[i][j]);
    for(int i = 1; i <= n; i++)
    {
        if(vs[i])
            Ls[i] -= a;
        if(vt[i])
            Lt[i] += a;
    }
}
void KM()
{
    memset(p, -1, sizeof(p));
    memset(Lt, 0, sizeof(Lt));
    memset(Ls, 0, sizeof(Ls));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            Ls[i] = max(Ls[i], Map[i][j]);
    for(int i = 1; i <= n; i++)
    {
        while(1)
        {
            memset(vs, false, sizeof(vs));
            memset(vt, false, sizeof(vt));
            if(dfs(i))
                break;
            else
                update();
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans += Map[p[i]][i];
    printf("%d\n", ans);
}
int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                scanf("%d", &Map[i][j]);
        KM();
    }
    return 0;
}
时间复杂度为0（n^3） 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 300 + 10;
int sx[maxn], sy[maxn], vx[maxn], vy[maxn], match[maxn];
int money[maxn][maxn], slack[maxn];
int n;
void chushihua()
{
    memset(sy, 0, sizeof(sy));
    for(int i = 1; i <= n; i++)
    {
        sx[i] = 1;
        for(int j = 1; j <= n; j++)
        {
            scanf("%d", &money[i][j]);
            sx[i] = max(sx[i], money[i][j]);
        }
    }
}
bool dfs(int x)
{
    vx[x] = true;
    for(int i = 1; i <= n; i++)
    {
        int xx= sx[x] + sy[i] - money[x][i];
        if(!vy[i] && !xx)
        {
            vy[i] = true;
            if(match[i]==-1 || dfs(match[i]))
            {
                match[i] = x;
                return true;
            }
        }
        else if(slack[i] > xx)
            slack[i] = xx;
    }
    return false;
}
void bestmatch()
{
    for(int i = 1; i <= n; i++)
    {
        while(1)
        {
            memset(vx, false, sizeof(vx));
            memset(vy, false, sizeof(vy));
            memset(slack, 0x3f, sizeof(slack));
            if(dfs(i))
                break;
            int dd = inf;
            for(int i = 1; i <= n; i++)
                if(!vy[i] && dd>slack[i])
                    dd = slack[i];
            for(int i = 1; i <= n; i++)
            {
                if(vx[i])
                    sx[i] -= dd;
                if(vy[i])
                    sy[i] += dd;
            }
        }
    }
}
int main()
{
    while(~scanf("%d", &n))
    {
        memset(match, -1, sizeof(match));
        chushihua();
        bestmatch();
        int sum = 0;
        for(int i = 1; i <= n; i++)
            sum += money[match[i]][i];
        printf("%d\n", sum);
    }
    return 0;
}

poj2195（此题可以用费用流做）

最小权最优匹配模版：

求最小权最优匹配有两种方案：

（1）把所有的权值取反， 求最大权匹配，得到结果取反

（2）顶标lx【i】表示与顶点i相连的所有边的最小值； 顶标ly【j】为零（为了保证lx【i】+ly【j】<=w【i】【j】）

          当不存在完备匹配时，进行扩展时，顶标lx加上扩展量， 顶标ly减去扩展量

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
struct Info
{
    int x, y;
};
char s[105];
int sm[maxn], sh[maxn];
int w[maxn][maxn], n;
int p[maxn];
int lx[maxn], ly[maxn];
bool vx[maxn], vy[maxn];
int slack[maxn];
Info kk[maxn], tt[maxn];
void inin(int N, int M)
{
    int cntm, cnth;
    cntm = cnth = 0;
    memset(w, 0, sizeof(w));
    for(int i = 1; i <= N; i++)
    {
        scanf("%s", s);
        for(int j = 0; j < M; j++)
        {
            if(s[j] == 'm')
            {
                cntm++;
                kk[cntm].x = i;
                kk[cntm].y = j + 1;
            }
            else if(s[j] == 'H')
            {
                cnth++;
                tt[cnth].x = i;
                tt[cnth].y = j + 1;
            }
        }
    }
    n = cntm;
    for(int i = 1; i <= n; i++)
    {
        lx[i] = inf;
        ly[i] = 0;
        for(int j = 1; j <= n; j++)
        {
            int dd = abs(kk[i].x-tt[j].x) + abs(kk[i].y-tt[j].y);
            w[i][j] = dd;
            if(lx[i] > dd)
                lx[i] = dd;
        }
    }
}
bool dfs(int i)
{
    vx[i] = true;
    for(int j = 1; j <= n; j++)
    {
        int xx = w[i][j] - lx[i] - ly[j];
        if(!vy[j] && !xx)
        {
            vy[j] = true;
            if(p[j]==-1 || dfs(p[j]))
            {
                p[j] = i;
                return true;
            }
        }
        else if(slack[j] > xx)
            slack[j] = xx;
    }
    return 0;
}
void solve()
{
    memset(p, -1, sizeof(p));
    for(int i = 1; i <= n; i++)
        while(1)
        {
            memset(vx, false, sizeof(vx));
            memset(vy, false, sizeof(vy));
            memset(slack, 0x3f, sizeof(slack));
            if(dfs(i))
                break;
            int dd = inf;
            for(int i = 1; i <= n; i++)
                if(!vy[i] && dd>slack[i])
                    dd = slack[i];
            for(int i = 1; i <= n; i++)
            {
                if(vx[i])
                    lx[i] += dd;
                if(vy[i])
                    ly[i] -= dd;
            }
        }
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans += w[p[i]][i];
    printf("%d\n", ans);
}
int main()
{
    int N, M;
    while(scanf("%d%d", &N, &M), N||M)
    {
        inin(N, M);
        solve();
    }
    return 0;
}





标签：

相关文章