uniolympiads English

Μέγιστη ροή (Dinic)

Η μέγιστη ροή από το ss στο tt και, από το τελευταίο BFS, μια ελάχιστη τομή. Πάνω της στηρίζονται ταίριασμα σε διμερή γράφο και ξένες διαδρομές.

Πότε

Το σήμα είναι συνήθως έμμεσο: «το μέγιστο πλήθος ζευγαριών», «το ελάχιστο πλήθος δρόμων που πρέπει να κλείσεις ώστε να μην πηγαίνεις από το 11 στο nn», «πόσες διαδρομές χωρίς κοινές ακμές». Με nn μέχρι μερικές εκατοντάδες ή χιλιάδες, η ροή είναι συχνά η απάντηση.

Η ιδέα

Κάθε ακμή έχει χωρητικότητα και μια αντίστροφη ακμή με χωρητικότητα 0. Όταν στέλνεις ροή ff από μια ακμή, η χωρητικότητά της μειώνεται κατά ff και της αντίστροφης αυξάνεται κατά ff. Έτσι ένα μεταγενέστερο μονοπάτι μπορεί να «πάρει πίσω» ροή που στάλθηκε λάθος.

Ο Dinic δουλεύει σε φάσεις:

  1. BFS από το ss στον υπολειπόμενο γράφο: κάθε κορυφή παίρνει επίπεδο.
  2. DFS που χρησιμοποιεί μόνο ακμές από το επίπεδο ℓ\ell στο ℓ+1\ell + 1, μέχρι να μη χωράει άλλη ροή (blocking flow). Ο δείκτης it[u] θυμάται από ποια ακμή να συνεχίσει, ώστε μια ακμή που «νεκρώθηκε» να μην ξανακοιταχτεί στην ίδια φάση.

Η απόσταση του tt αυξάνεται γνησίως σε κάθε φάση, άρα οι φάσεις είναι το πολύ nn. Συνολικά O(V2E)O(V^2 E) στη χειρότερη περίπτωση, O(EV)O(E\sqrt{V}) για ταίριασμα σε διμερή γράφο. Στην πράξη είναι πολύ πιο γρήγορος.

Ελάχιστη τομή. Όταν τελειώσει, οι κορυφές που φτάνει το τελευταίο BFS (level != -1) είναι η πλευρά του ss. Οι ακμές από αυτές προς τις υπόλοιπες είναι μια ελάχιστη τομή, και η χωρητικότητά της ισούται με τη ροή (θεώρημα max-flow min-cut). Το test επαληθεύει και τα δύο, συγκρίνοντας με απαρίθμηση όλων των τομών.

Τρία προβλήματα, μία κατασκευή

  • Download Speed: η ροή όπως είναι.
  • Police Chase: η ελάχιστη τομή, με χωρητικότητα 1 ανά δρόμο και προς τις δύο κατευθύνσεις.
  • School Dance: πηγή → αγόρια (1), αγόρι → κορίτσι (1), κορίτσια → καταβόθρα (1). Η ροή είναι το μέγιστο ταίριασμα· τα ζευγάρια είναι οι ακμές αγόρι → κορίτσι με κορεσμένη χωρητικότητα.

Παγίδες

  • Μη κατευθυνόμενη ακμή: δύο κλήσεις addEdge, μία για κάθε φορά.
  • Η DFS είναι αναδρομική, αλλά το βάθος της είναι το πολύ η απόσταση του tt, δηλαδή <n< n. Για τα μεγέθη όπου η ροή είναι η σωστή επιλογή, αυτό είναι ασφαλές.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/dinic.cpp
// Maximum flow, Dinic's algorithm. O(V^2 E) in general, O(E sqrt V) for bipartite matching.
// BFS builds the level graph; DFS sends blocking flow along edges with level[v] = level[u] + 1.
// it[u] remembers the next edge to try, so dead edges are not scanned twice in one phase.
// After maxFlow, the vertices with level != -1 form the source side of a minimum cut.

struct Dinic {
    struct Edge {
        int to;
        ll cap;
    };
    int n;
    vector<Edge> edges;
    vector<vector<int>> g;
    vector<int> level;
    vector<int> it;

    Dinic(int vertices) : n(vertices), g(vertices), level(vertices), it(vertices) {}

    // Edge i and its reverse i ^ 1 are stored next to each other.
    void addEdge(int u, int v, ll cap) {
        g[u].push_back(edges.size());
        edges.push_back({v, cap});
        g[v].push_back(edges.size());
        edges.push_back({u, 0});
    }

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int id : g[u]) {
                if (edges[id].cap > 0 && level[edges[id].to] == -1) {
                    level[edges[id].to] = level[u] + 1;
                    q.push(edges[id].to);
                }
            }
        }
        return level[t] != -1;
    }

    ll dfs(int u, int t, ll pushed) {
        if (u == t) {
            return pushed;
        }
        for (; it[u] < (int)g[u].size(); it[u]++) {
            int id = g[u][it[u]];
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == level[u] + 1) {
                ll got = dfs(v, t, min(pushed, edges[id].cap));
                if (got > 0) {
                    edges[id].cap -= got;
                    edges[id ^ 1].cap += got;
                    return got;
                }
            }
        }
        return 0;
    }

    ll maxFlow(int s, int t) {
        ll flow = 0;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            while (true) {
                ll f = dfs(s, t, LLONG_MAX);
                if (f == 0) {
                    break;
                }
                flow += f;
            }
        }
        return flow;
    }
};

Ελέγχθηκε σε 1.500 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.