Алгоритм Форда-Фалкерсона: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (→Ссылки) |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 6: | Строка 6: | ||
struct Edge { | struct Edge { | ||
int a, b, cap, flow; | int a, b, cap, flow; | ||
Edge(int a, int b, int cap) : a(a), b(b), cap(cap), flow( | Edge(int a, int b, int cap, int flow) : a(a), b(b), cap(cap), flow(flow) {} | ||
}; | }; | ||
vector<Edge> edges; | vector<Edge> edges; | ||
| Строка 36: | Строка 36: | ||
for (int i = 0; i < m; i++) { | for (int i = 0; i < m; i++) { | ||
scanf("%d%d%d", &a, &b, &cap); | scanf("%d%d%d", &a, &b, &cap); | ||
edges.push_back(Edge(a - 1, b - 1, cap)); | edges.push_back(Edge(a - 1, b - 1, cap, 0)); | ||
g[a - 1].push_back(edges.size() - 1); | g[a - 1].push_back(edges.size() - 1); | ||
edges.push_back(Edge(b - 1, a - 1, cap)); | edges.push_back(Edge(b - 1, a - 1, cap, cap)); | ||
g[b - 1].push_back(edges.size() - 1); | g[b - 1].push_back(edges.size() - 1); | ||
} | } | ||
Версия от 22:16, 23 мая 2015
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int a, b, cap, flow;
Edge(int a, int b, int cap, int flow) : a(a), b(b), cap(cap), flow(flow) {}
};
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, 0));
g[a - 1].push_back(edges.size() - 1);
edges.push_back(Edge(b - 1, a - 1, cap, 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);
}