Алгоритм Форда-Фалкерсона: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 3: | Строка 3: | ||
#include <vector> | #include <vector> | ||
using namespace std; | using namespace std; | ||
struct Edge { | struct Edge { | ||
int a, b, cap, flow; | int a, b, cap, flow; | ||
Edge(int a, int b, int cap | Edge(int a, int b, int cap) : a(a), b(b), cap(cap), flow(0) {} | ||
int other(int v) { | |||
return v == a ? b : a; | |||
} | |||
int capTo(int v) { | |||
return v == b ? cap - flow : flow; | |||
} | |||
void addFlowTo(int v, int f) { | |||
flow += (v == b ? f : -f); | |||
} | |||
}; | }; | ||
vector<Edge> edges; | vector<Edge> edges; | ||
int n, m, u[1010], | int n, m, u[1010], p[1010]; | ||
vector<int> g[1010]; | vector<int> g[1010]; | ||
bool dfs(int v, int vTarget) { | |||
u[v] = 1; | u[v] = 1; | ||
if (v == | if (v == vTarget) | ||
return | return 1; | ||
for (int i = 0; i < g[v].size(); i++) { | for (int i = 0; i < g[v].size(); i++) { | ||
int e = g[v][i], to = edges[e].other(v); | |||
if (!u[to] && edges[e].capTo(to)) { | |||
p[to] = e; | |||
if (dfs(to, vTarget)) | |||
return 1; | |||
} | |||
} | } | ||
return 0; | return 0; | ||
} | } | ||
int main() { | int main() { | ||
scanf("%d%d", &n, &m); | scanf("%d%d", &n, &m); | ||
| Строка 36: | Строка 42: | ||
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)); | ||
g[a - 1].push_back(edges.size() - 1); | g[a - 1].push_back(edges.size() - 1); | ||
g[b - 1].push_back(edges.size() - 1); | g[b - 1].push_back(edges.size() - 1); | ||
} | } | ||
int flow = 0; | int flow = 0; | ||
while (1) { | while (1) { | ||
fill(u, u + n, 0); | fill(u, u + n, 0); | ||
if (!dfs(0, n - 1)) | |||
break; | break; | ||
int deltaFlow = 1 << 30; | |||
for (int v = n - 1; v != 0; v = edges[p[v]].other(v)) | |||
deltaFlow = min(deltaFlow, edges[p[v]].capTo(v)); | |||
flow += deltaFlow; | flow += deltaFlow; | ||
for (int v = n - 1; v != 0; v = edges[p[v]].other(v)) | |||
edges[p[v]].addFlowTo(v, deltaFlow); | |||
} | } | ||
printf("%d", flow); | printf("%d", flow); | ||
} | } | ||
== Ссылки == | == Ссылки == | ||
* [http://algs4.cs.princeton.edu/lectures/64MaxFlow.pdf algs4.cs.princeton.edu/lectures — 6.4 Maximum Flow] | * [http://algs4.cs.princeton.edu/lectures/64MaxFlow.pdf algs4.cs.princeton.edu/lectures — 6.4 Maximum Flow] | ||
Версия от 22:06, 27 мая 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) : a(a), b(b), cap(cap), flow(0) {}
int other(int v) {
return v == a ? b : a;
}
int capTo(int v) {
return v == b ? cap - flow : flow;
}
void addFlowTo(int v, int f) {
flow += (v == b ? f : -f);
}
};
vector<Edge> edges;
int n, m, u[1010], p[1010];
vector<int> g[1010];
bool dfs(int v, int vTarget) {
u[v] = 1;
if (v == vTarget)
return 1;
for (int i = 0; i < g[v].size(); i++) {
int e = g[v][i], to = edges[e].other(v);
if (!u[to] && edges[e].capTo(to)) {
p[to] = e;
if (dfs(to, vTarget))
return 1;
}
}
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);
g[b - 1].push_back(edges.size() - 1);
}
int flow = 0;
while (1) {
fill(u, u + n, 0);
if (!dfs(0, n - 1))
break;
int deltaFlow = 1 << 30;
for (int v = n - 1; v != 0; v = edges[p[v]].other(v))
deltaFlow = min(deltaFlow, edges[p[v]].capTo(v));
flow += deltaFlow;
for (int v = n - 1; v != 0; v = edges[p[v]].other(v))
edges[p[v]].addFlowTo(v, deltaFlow);
}
printf("%d", flow);
}