Алгоритм Форда-Фалкерсона
Перейти к навигации
Перейти к поиску
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int a, b, cap, flow;
Edge(int a, int b, int cap) : a(a), b(b), cap(cap), flow(0) {}
};
vector<Edge> edges;
int n, m, u[1010], INF = 1 << 30;
vector<int> g[1010];
int findPath(int v, int bottleneckFlow) {
u[v] = 1;
if (v == n - 1)
return bottleneckFlow;
for (int i = 0; i < g[v].size(); i++) {
Edge &e = edges[g[v][i]], &re = edges[g[v][i] ^ 1];
if (!u[e.b] && e.cap > e.flow) {
int deltaFlow = findPath(e.b, min(bottleneckFlow, e.cap - e.flow));
if (deltaFlow) {
e.flow += deltaFlow;
re.flow -= deltaFlow;
return deltaFlow;
}
}
}
return 0;
}
int main() {
scanf("%d%d", &n, &m);
int a, b, cap;
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &a, &b, &cap);
edges.push_back(Edge(a - 1, b - 1, cap));
g[a - 1].push_back(edges.size() - 1);
edges.push_back(Edge(b - 1, a - 1, cap));
g[b - 1].push_back(edges.size() - 1);
}
int flow = 0;
while (1) {
fill(u, u + n, 0);
int deltaFlow = findPath(0, INF);
if (!deltaFlow)
break;
flow += deltaFlow;
}
printf("%d", flow);
}