Тармактагы агымдар

Максималдуу агым: кесүү жөнүндө теорема, Эдмондс-Карп алгоритми жана паросочетаниелерге колдонулушу.

Тармак — ар бир кырында өткөрүү жөндөмдүүлүгү бар багытталган граф. Максималдуу агым — s булагынан t агызгычка канча «суюктук» өткөрүүгө болот. Фундаменталдык теорема (Форд-Фалкерсон): максималдуу агым минималдуу кесүүгө барабар — өчүрүлгөндө s менен t айрылып калган кырлардын минималдуу суммардык өткөрүү жөндөмдүүлүгүнө. Ошондуктан агымдар менен «канча өткөрсө болот» жана «эмнени кесиш керек» деген маселелердин экөө тең чечилет. Эдмондс-Карп алгоритми: s тен t га чейин оң калдык өткөрүү жөндөмдүүлүктөрү бар жол бар болуп турганда (аны BFS менен издейбиз), ал жол боюнча агым өткөрөбүз жана КАЛДЫК тармакты жаңылайбыз: түз кырларды азайтабыз, тескерилерин көбөйтөбүз. Тескери кырлар — ачкыч: алар «оюн өзгөртүп», мурда өткөрүлгөн агымды кайра багыттоого мүмкүндүк берет.

Өзүңүз байкап көрүңүз — кодду өзгөртсө болот

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

const long long INF = 1e18;
int n, m;
std::vector<std::vector<long long>> cap;
std::vector<std::vector<int>> g;

long long bfs(int s, int t, std::vector<int> &parent) {
    std::fill(parent.begin(), parent.end(), -1);
    parent[s] = s;
    std::queue<std::pair<int, long long>> q;
    q.push({s, INF});

while (!q.empty()) {
        auto [v, flow] = q.front();
        q.pop();
        for (int to : g[v]) {
            if (parent[to] == -1 && cap[v][to] > 0) {
                parent[to] = v;
                long long nf = std::min(flow, cap[v][to]);
                if (to == t) return nf;
                q.push({to, nf});
            }
        }
    }
    return 0;
}

int main() {
    std::cin >> n >> m;
    cap.assign(n + 1, std::vector<long long>(n + 1, 0));
    g.assign(n + 1, {});

for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        if (cap[a][b] == 0 && cap[b][a] == 0) {
            g[a].push_back(b);
            g[b].push_back(a); // обратное ребро для остаточной сети
        }
        cap[a][b] += c;
    }

long long flow = 0, add;
    std::vector<int> parent(n + 1);
    while ((add = bfs(1, n, parent)) > 0) {
        flow += add;
        int v = n;
        while (v != 1) {
            int p = parent[v];
            cap[p][v] -= add;
            cap[v][p] += add;
            v = p;
        }
    }
    std::cout << "Максимальный поток: " << flow << "\n";
    return 0;
}

Киргизүү маалыматтары (мисал — өзгөртсө болот)

Эдмондс-Карп, булак 1, агызгыч n. Киргизиңиз: 4 5, андан кийин «a b өткөрүү»: 1 2 3, 1 3 2, 2 3 1, 2 4 2, 3 4 3

Мисалда максималдуу агым 5ке барабар: 2 бирдик 1→2→4 жолу менен, 2 бирдик 1→3→4 менен жана дагы 1 бирдик 1→2→3→4 менен. Эдмондс-Карптын татаалдыгы — O(V·E²); тыгыз маселелер үчүн тезирээк Диниц алгоритми бар. Башкы практикалык колдонулушу — эки үлүштүү паросочетаниелер: ар бири бир гана түгөйдө болгон «студент-долбоор» түгөйлөрүнүн максималдуу саны. Тармак куруңуз: булак → студенттер (өткөрүү 1) → жарактуу долбоорлор (өткөрүү 1) → агызгыч. Максималдуу агым = максималдуу паросочетание.

Тапшырма: «3 жумушчу, 3 тапшырма, ким эмнени билет» маселесин кагазда тармак катары моделдеп, жогорудагы программадан өткөрүңүз (номерлеңиз: 1 — булак, 2-4 — жумушчулар, 5-7 — тапшырмалар, 8 — агызгыч). Сабакты өттүм деп белгилеңиз.