题目链接

https://www.luogu.com.cn/problem/P6577

题目大意

给定一个二分图，其左右点的个数各为 \(n\)，带权边数为 \(m\)，保证存在完美匹配。

求一种完美匹配的方案，使得最终匹配边的边权之和最大。

题目解析

二分图最大权完美匹配，一般用 \(KM\) 算法完成。

基础版的 \(KM\) 算法，是匈牙利算法的改进，依然采用 \(DFS\) 策略，速度较慢。

而改进版的 \(KM\) 算法采用 \(BFS\) 策略，有效提升速度。

点数为 \(n\)，边数为 \(m\) 。

时间复杂度： \(O(n^2 m)\)

参考代码

基础版（会超时）

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

const int N = 505;

int mp[N][N], lx[N], ly[N], visx[N], visy[N], match[N];

int n, m, minz, k;

bool dfs(int x, int K)

{

    visx[x] = K;

    for (int y = 1; y <= n; ++y) {

        if (visy[y] != K && mp[x][y] != INF) {

            int t = lx[x] + ly[y] - mp[x][y];

            if (!t) {

                visy[y] = K;

                if (!match[y] || dfs(match[y], K)) {

                    match[y] = x;

                    return true;

                }

            }

            else minz = min(minz, t);

        }

    }

    return false;

}

void KM()

{

    for (int i = 1; i <= n; ++i) {

        while (1) {

            minz = INF;

            if (dfs(i, ++k)) break;

            for (int j = 1; j <= n; ++j) {

                if (visx[j] == k) lx[j] -= minz;

                if (visy[j] == k) ly[j] += minz;

            }

        }

    }

}

int main()

{

    scanf("%d%d", &n, &m);

    memset(mp, INF, sizeof mp);

    for (int i = 1; i <= n; ++i) lx[i] = -INF;

    for (int i = 0; i < m; ++i) {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        mp[u][v] = w;

        lx[u] = max(lx[u], w);

    }

    KM();

    ll ans = 0;

    for (int i = 1; i <= n; ++i) ans += mp[match[i]][i];

    printf("%lld\n", ans);

    for (int i = 1; i <= n; ++i) printf("%d ", match[i]);

    putchar('\n');

    return 0;

}

改进版

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

const int N = 505;

int mp[N][N], lx[N], ly[N], visy[N], matchy[N], pr[N], slack[N];

int n, m, minz, k;

void bfs(int x, int K)

{

    int y = 0, yy = 0;

    memset(pr, 0, sizeof pr);

    memset(slack, INF, sizeof slack);

    matchy[y] = x;

    while (true)

    {

        x = matchy[y];

        visy[y] = K;

        for (int i = 1; i <= n; ++i)

        {

            if (visy[i] == K || mp[x][i] == -INF) continue;

            int t = lx[x] + ly[i] - mp[x][i];

            if (slack[i] > t)

            {

                slack[i] = t;

                pr[i] = y;

            }

        }

        minz = INF;

        for (int i = 1; i <= n; ++i) {

            if (visy[i] != K && slack[i] < minz) {

                minz = slack[i];

                yy = i;

                if (!minz) break;

            }

        }

        if (minz) {

            for(int i = 0; i <= n; ++i)

            {

                if (visy[i] == K) lx[matchy[i]] -= minz, ly[i] += minz;

                else slack[i] -= minz;

            }

        }

        y = yy;

        if (!matchy[y]) break;

    }

    while (y) {

        matchy[y] = matchy[pr[y]];

        y = pr[y];

    }

}

void KM()

{

    for (int i = 1; i <= n; ++i) {

        bfs(i, ++k);

    }

}

int main()

{

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) {

        for (int j = 1; j <= n; ++j) {

            mp[i][j] = -INF;

        }

    }

    for (int i = 1; i <= n; ++i) lx[i] = -INF;

    for (int i = 0; i < m; ++i) {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        mp[u][v] = w;

        lx[u] = max(lx[u], w);

    }

    KM();

    ll ans = 0;

    for (int i = 1; i <= n; ++i) ans += mp[matchy[i]][i];

    printf("%lld\n", ans);

    for (int i = 1; i <= n; ++i) printf("%d ", matchy[i]);

    putchar('\n');

    return 0;

}

感谢支持！

巴特西

【模板】二分图最大权完美匹配（KM算法）/洛谷P6577

题目链接

题目大意

题目解析

参考代码

最新文章

热门文章