kuhnmunkres.cpp

Bài toán

Tìm bộ ghép cực đại với trọng số cực tiểu bằng phương pháp Kuhn-Munkres.

Độ phức tạp

O(n^3)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <map>

#include <queue>

#include <vector>

#include <iostream>

#include <algorithm>

#include <cassert>

using namespace std;

#define N 1003

int n;

int c[N][N];

int f[N], d[N], Decision[N];

int Assigned[N], Visited[N];

vector<int> Left, Right;

queue<int> qu;

bool assignable(int &a, int b) {

    if (a == 0)

        a = b;

    else

        return false;

    return true;

}

bool minimize(int &a, int b) {

    if (a > b)

        a = b;

    else

        return false;

    return true;

}

bool maximize(int &a, int b) {

    if (a < b)

        a = b;

    else

        return false;

    return true;

}

int bfs_next() {

    while (qu.size()) {

        int u = qu.front();

        qu.pop();

        for (int v : Right) {

            if (c[u][v] + f[u] + f[v] == 0)

                if (assignable(Visited[v], u)) {

                    if (!Assigned[v])

                        return v;

                    Visited[Assigned[v]] = v;

                    qu.push(Assigned[v]);

                }

            if (minimize(d[v], c[u][v] + f[u] + f[v]))

                Decision[v] = u;

        }

    }

    return 0;

}

int bfs_first(int Start) {

    while (qu.size())

        qu.pop();

    for (int i = 1; i <= 2 * n; ++i) Visited[i] = 0;

    for (int u : Right) {

        d[u] = c[Start][u] + f[Start] + f[u];

        Decision[u] = Start;

    }

    Visited[Start] = -1, qu.push(Start);

    return bfs_next();

}

bool adjust() {

    int Delta = 0x11112222;

    for (int u : Right) if (!Visited[u]) minimize(Delta, d[u]);

    if (Delta >= 0x11112222)

        return false;

    assert(Delta != 0);

    for (int u : Left) if (Visited[u]) f[u] -= Delta;

    for (int u : Right) if (Visited[u]) f[u] += Delta;

    for (int u : Right) if (!Visited[u]) {

        d[u] -= Delta;

        if (d[u] == 0)

            qu.push(Decision[u]);

    }

    return true;

}

void enlarge(int u) {

    while (u > 0) {

        int y = u, x = Visited[y];

        u = Assigned[x];

        Assigned[x] = y;

        Assigned[y] = x;

    }

}

map<int, int> Map[N];

int force(int Pos, int Used) {

    int Answer = 0x11112222;

    if (Pos == n + 1)

        return 0;

    if (Map[Pos].count(Used))

        return Map[Pos][Used];

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

        if ((1 << i - 1) & ~Used)

            minimize(Answer, force(Pos + 1, Used | (1 << i - 1)) + c[Pos][i + n]);

    return Map[Pos][Used] = Answer;

}

int main() {

    cin >> n;

    srand(n * 1000);

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

        //cin >> c[i][j+n];

        c[i][j + n] = rand() % 100 * 10;

        cout << c[i][j + n] << (j == n ? "\n" : " ");

    }

    for (int i = 1; i <= n; ++i) Left.push_back(i);

    for (int i = 1; i <= n; ++i) Right.push_back(i + n);

    for (int u : Left) {

        int x = bfs_first(u);

        while (x == 0) {

            if (!adjust())

                break;

            else

                x = bfs_next();

        }

        enlarge(x);

    }

    int Answer = 0;

    for (int i = 1; i <= n; ++i) Answer += c[i][Assigned[i]];

    cout << Answer << endl;

    cout << force(1, 0) << endl;

    cin.ignore(2);

}

Nhận xét