Алгоритм Куна: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «== Ссылки == * [http://e-maxx.ru/algo/kuhn_matching e-maxx.ru — Алгоритм Куна нахождения наибольшего паросоче…»)
 
Нет описания правки
 
(не показано 5 промежуточных версий этого же участника)
Строка 1: Строка 1:
{|width=100%
|width=50%|
'''Простой вариант'''
bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, vector<int> &pairFromA) {
    visited[vFromA] = 1;
    for (int vFromB : graphA[vFromA]) {
        int &toFromA = pairFromA[vFromB];
        if (toFromA == -1 || !visited[toFromA] && dfs(graphA, toFromA, visited, pairFromA)) {
            toFromA = vFromA;
            return 1;
        }
    }
    return 0;
}
vector<int> kuhn(vector<vector<int>> &graphA, int vertexCountB) {
    vector<int> pairFromA(vertexCountB, -1);
    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        vector<int> visited(graphA.size());
        dfs(graphA, vFromA, visited, pairFromA);
    }
    return pairFromA;
}
|width=50%|
'''Более эффективный вариант без обнуления visited'''
bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, {{Changed|int i,}} vector<int> &pairFromA) {
    visited[vFromA] = {{Changed|i}};
    for (int vFromB : graphA[vFromA]) {
        int &toFromA = pairFromA[vFromB];
        if (toFromA == -1 || {{Changed|1=visited[toFromA] != i}} && dfs(graphA, toFromA, visited, {{Changed|i,}} pairFromA)) {
            toFromA = vFromA;
            return 1;
        }
    }
    return 0;
}
vector<int> kuhn(vector<vector<int>> &graphA, int vertexCountB) {
    {{Changed|1=vector<int> visited(graphA.size(), -1);}}
    vector<int> pairFromA(vertexCountB, -1);
    for (int vFromA = 0; vFromA < graphA.size(); vFromA++)
        dfs(graphA, vFromA, visited, {{Changed|vFromA,}} pairFromA);
    return pairFromA;
}
|}
{|width=100%
|width=50%|
vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) {
    vector<int> greedyVisited(graphA.size());
    vector<int> pairFromA(vertexCountB, -1);
    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        for (int vFromB : graphA[vFromA]) {
            if (pairFromA[vFromB] == -1) {
                greedyVisited[vFromA] = 1;
                pairFromA[vFromB] = vFromA;
                break;
            }
        }
    }
    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        if (!greedyVisited[vFromA]) {
            vector<int> visited(graphA.size());
            dfs(graphA, vFromA, visited, pairFromA);
        }
    }
    return pairFromA;
}
|width=50%|
vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) {
    vector<int> greedyVisited(graphA.size());
    vector<int> pairFromA(vertexCountB, -1);
    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        for (int vFromB : graphA[vFromA]) {
            if (pairFromA[vFromB] == -1) {
                greedyVisited[vFromA] = 1;
                pairFromA[vFromB] = vFromA;
                break;
            }
        }
    }
    {{Changed|1=vector<int> visited(graphA.size(), -1);}}
    for (int vFromA = 0; vFromA < graphA.size(); vFromA++)
        if (!greedyVisited[vFromA])
            dfs(graphA, vFromA, visited, {{Changed|vFromA,}} pairFromA);
    return pairFromA;
}
|}
== Ссылки ==
== Ссылки ==
* [http://e-maxx.ru/algo/kuhn_matching e-maxx.ru &mdash; Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе]
Теория:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%83%D0%BD%D0%B0_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F neerc.ifmo.ru/wiki &mdash; Алгоритм Куна для поиска максимального паросочетания]
* [http://e-maxx.ru/algo/kuhn_matching e-maxx.ru — Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе]
* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxMatching.java CodeLibrary &mdash; Maximum matching for bipartite graph. Kuhn's algorithm in O(V^3)]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%83%D0%BD%D0%B0_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F neerc.ifmo.ru/wiki — Алгоритм Куна для поиска максимального паросочетания]
* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxMatching2.java CodeLibrary &mdash; Maximum matching for bipartite graph. Kuhn's algorithm in O(EV)]
* [https://algorithmica.org/ru/matching algorithmica.org — Паросочетания]
* [http://github.com/ADJA/algos/blob/master/Graphs/BipartiteMatchingKuhn.cpp Algos &mdash; Kuhn algorithm for maximum matching in bipartite graph]
* [https://codeforces.com/blog/entry/17023 Codeforces — Паросочетание. Быстрый Кун]
* [http://brilliant.org/wiki/matching-algorithms Brilliant.org — Matching Algorithms]
Код:
* [https://github.com/indy256/codelibrary/blob/master/cpp/graphs/matchings/max_bipartite_matching_EV.cpp codelibrary/cpp/graphs/matchings/max_bipartite_matching_EV.cpp]
* [http://github.com/ADJA/algos/blob/master/Graphs/BipartiteMatchingKuhn.cpp algos/Graphs/BipartiteMatchingKuhn.cpp]

Текущая версия от 03:16, 25 февраля 2023

Простой вариант 

bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, vector<int> &pairFromA) {
    visited[vFromA] = 1;

    for (int vFromB : graphA[vFromA]) {
        int &toFromA = pairFromA[vFromB];

        if (toFromA == -1 || !visited[toFromA] && dfs(graphA, toFromA, visited, pairFromA)) {
            toFromA = vFromA;
            return 1;
        }
    }

    return 0;
}

vector<int> kuhn(vector<vector<int>> &graphA, int vertexCountB) {
    vector<int> pairFromA(vertexCountB, -1);

    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        vector<int> visited(graphA.size());
        dfs(graphA, vFromA, visited, pairFromA);
    }

    return pairFromA;
}

Более эффективный вариант без обнуления visited 

bool dfs(vector<vector<int>> &graphA, int vFromA, vector<int> &visited, int i, vector<int> &pairFromA) {
    visited[vFromA] = i;

    for (int vFromB : graphA[vFromA]) {
        int &toFromA = pairFromA[vFromB];

        if (toFromA == -1 || visited[toFromA] != i && dfs(graphA, toFromA, visited, i, pairFromA)) {
            toFromA = vFromA;
            return 1;
        }
    }

    return 0;
}

vector<int> kuhn(vector<vector<int>> &graphA, int vertexCountB) {
    vector<int> visited(graphA.size(), -1);
    vector<int> pairFromA(vertexCountB, -1);

    for (int vFromA = 0; vFromA < graphA.size(); vFromA++)
        dfs(graphA, vFromA, visited, vFromA, pairFromA);

    return pairFromA;
}


vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) {
    vector<int> greedyVisited(graphA.size());
    vector<int> pairFromA(vertexCountB, -1);

    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        for (int vFromB : graphA[vFromA]) {
            if (pairFromA[vFromB] == -1) {
                greedyVisited[vFromA] = 1;
                pairFromA[vFromB] = vFromA;
                break;
            }
        }
    }

    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        if (!greedyVisited[vFromA]) {
            vector<int> visited(graphA.size());
            dfs(graphA, vFromA, visited, pairFromA);
        }
    }

    return pairFromA;
}

vector<int> kuhnWithGreedyInitialization(vector<vector<int>> &graphA, int vertexCountB) {
    vector<int> greedyVisited(graphA.size());
    vector<int> pairFromA(vertexCountB, -1);

    for (int vFromA = 0; vFromA < graphA.size(); vFromA++) {
        for (int vFromB : graphA[vFromA]) {
            if (pairFromA[vFromB] == -1) {
                greedyVisited[vFromA] = 1;
                pairFromA[vFromB] = vFromA;
                break;
            }
        }
    }

    vector<int> visited(graphA.size(), -1);

    for (int vFromA = 0; vFromA < graphA.size(); vFromA++)
        if (!greedyVisited[vFromA])
            dfs(graphA, vFromA, visited, vFromA, pairFromA);

    return pairFromA;
}

Ссылки

Теория:

Код:

Источник — https://acm.khpnets.info/w39/index.php?title=Алгоритм_Куна&oldid=2847