ЯсноПонятно24

Вот пример кода на C++ для нахождения максимального паросочетания в двудольном графе с использованием алгоритма сжатия цветков:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 1000;

vector<int> g[MAXN];
int match[MAXN], p[MAXN], base[MAXN], blossom[MAXN];
bool used[MAXN], blossom_end[MAXN];

int lca(int a, int b) {
    vector<bool> used(MAXN, false);
    while (true) {
        a = base[a];
        used[a] = true;
        if (match[a] == -1) {
            break;
        }
        a = p[match[a]];
    }
    while (true) {
        b = base[b];
        if (used[b]) {
            return b;
        }
        b = p[match[b]];
    }
}

void mark_path(int v, int b, int children) {
    while (base[v] != b) {
        blossom[base[v]] = blossom[base[match[v]]] = true;
        p[v] = children;
        children = match[v];
        v = p[match[v]];
    }
}

int find_path(int root, int n) {
    fill(used, used + n, false);
    fill(p, p + n, -1);
    for (int i = 0; i < n; ++i) {
        base[i] = i;
    }

    queue<int> q;
    q.push(root);
    used[root] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int i = 0; i < g[v].size(); ++i) {
            int to = g[v][i];
            if (base[v] == base[to] || match[v] == to) {
                continue;
            }
            if (to == root || (match[to] != -1 && p[match[to]] != -1)) {
                int curbase = lca(v, to);
                fill(blossom, blossom + n, false);
                mark_path(v, curbase, to);
                mark_path(to, curbase, v);
                for (int i = 0; i < n; ++i) {
                    if (blossom[base[i]]) {
                        base[i] = curbase;
                        if (!used[i]) {
                            used[i] = true;
                            q.push(i);
                        }
                    }
                }
            } else if (p[to] == -1) {
                p[to] = v;
                if (match[to] == -1) {
                    return to;
                }
                to = match[to];
                used[to] = true;
                q.push(to);
            }
        }
    }

    return -1;
}

int max_matching(int n) {
    fill(match, match + n, -1);
    for (int i = 0; i < n; ++i) {
        if (match[i] == -1) {
            int v = find_path(i, n);
            while (v != -1) {
                int pv = p[v], ppv = match[pv];
                match[v] = pv;
                match[pv] = v;
                v = ppv;
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; ++i) {
        if (match[i] != -1) {
            ++res;
        }
    }

    return res / 2;
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    cout << max_matching(n) << endl;

    return 0;
}

Этот код реализует алгоритм сжатия цветков для нахождения максимального паросочетания в двудольном графе.