Μέγιστη ροή (Dinic)
Η μέγιστη ροή από το στο και, από το τελευταίο BFS, μια ελάχιστη τομή. Πάνω της στηρίζονται ταίριασμα σε διμερή γράφο και ξένες διαδρομές.
Πότε
Το σήμα είναι συνήθως έμμεσο: «το μέγιστο πλήθος ζευγαριών», «το ελάχιστο πλήθος δρόμων που πρέπει να κλείσεις ώστε να μην πηγαίνεις από το στο », «πόσες διαδρομές χωρίς κοινές ακμές». Με μέχρι μερικές εκατοντάδες ή χιλιάδες, η ροή είναι συχνά η απάντηση.
Η ιδέα
Κάθε ακμή έχει χωρητικότητα και μια αντίστροφη ακμή με χωρητικότητα 0. Όταν στέλνεις ροή από μια ακμή, η χωρητικότητά της μειώνεται κατά και της αντίστροφης αυξάνεται κατά . Έτσι ένα μεταγενέστερο μονοπάτι μπορεί να «πάρει πίσω» ροή που στάλθηκε λάθος.
Ο Dinic δουλεύει σε φάσεις:
- BFS από το στον υπολειπόμενο γράφο: κάθε κορυφή παίρνει επίπεδο.
- DFS που χρησιμοποιεί μόνο ακμές από το επίπεδο στο , μέχρι να μη χωράει άλλη ροή (blocking flow). Ο δείκτης
it[u]θυμάται από ποια ακμή να συνεχίσει, ώστε μια ακμή που «νεκρώθηκε» να μην ξανακοιταχτεί στην ίδια φάση.
Η απόσταση του αυξάνεται γνησίως σε κάθε φάση, άρα οι φάσεις είναι το πολύ . Συνολικά στη χειρότερη περίπτωση, για ταίριασμα σε διμερή γράφο. Στην πράξη είναι πολύ πιο γρήγορος.
Ελάχιστη τομή. Όταν τελειώσει, οι κορυφές που φτάνει το τελευταίο BFS (level != -1) είναι η πλευρά του . Οι ακμές από αυτές προς τις υπόλοιπες είναι μια ελάχιστη τομή, και η χωρητικότητά της ισούται με τη ροή (θεώρημα max-flow min-cut). Το test επαληθεύει και τα δύο, συγκρίνοντας με απαρίθμηση όλων των τομών.
Τρία προβλήματα, μία κατασκευή
Download Speed: η ροή όπως είναι.Police Chase: η ελάχιστη τομή, με χωρητικότητα 1 ανά δρόμο και προς τις δύο κατευθύνσεις.School Dance: πηγή → αγόρια (1), αγόρι → κορίτσι (1), κορίτσια → καταβόθρα (1). Η ροή είναι το μέγιστο ταίριασμα· τα ζευγάρια είναι οι ακμές αγόρι → κορίτσι με κορεσμένη χωρητικότητα.
Παγίδες
- Μη κατευθυνόμενη ακμή: δύο κλήσεις
addEdge, μία για κάθε φορά. - Η DFS είναι αναδρομική, αλλά το βάθος της είναι το πολύ η απόσταση του , δηλαδή . Για τα μεγέθη όπου η ροή είναι η σωστή επιλογή, αυτό είναι ασφαλές.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// 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
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Download Speed · Graph Algorithms
- Police Chase · Graph Algorithms
- School Dance · Graph Algorithms
- Distinct Routes · Graph Algorithms
Περισσότερα στο USACO Guide
- Maximum Flow · usaco.guide/adv/max-flow
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.