# Cod sursa(job #1709589)

Utilizator Data 28 mai 2016 12:59:25 Flux maxim 20 cpp done Arhiva educationala 1.41 kb
``````#include <stdio.h>
#include <vector>
#include <queue>

#define maxdim 1005
#define INF (1 << 29)

using namespace std;

int n, m, S, D;
int cap[maxdim][maxdim], F[maxdim][maxdim], viz[maxdim], T[maxdim];
vector<int> G[maxdim];

inline bool bfs() {
for (int i = 1; i <= D; ++i) {
viz[i] = T[i] = 0;
}
queue<int> q;
q.push(S);
viz[S] = 1;

int ok = 0;
while (!q.empty()) {
int nod = q.front(); q.pop();
for (int vecin : G[nod]) {
if (!viz[vecin] && cap[nod][vecin] > F[nod][vecin]) {
if (vecin == D) {
ok = 1;
continue;
}
T[vecin] = nod;
viz[vecin] = 1;
q.push(vecin);
}
}
}

return ok;
}

int flux() {
int f = 0;

while (bfs()) {

for (int nod : G[D]) {
T[D] = nod;
int crtf = INF;
for (int x = D; T[x]; x = T[x]) {
crtf = min(crtf, cap[T[x]][x] - F[T[x]][x]);
}
f += crtf;
for (int x = D; T[x]; x = T[x]) {
F[T[x]][x] += crtf;
F[x][T[x]] -= crtf;
}
}
}

return f;
}

void add_edge(int x, int y) {
G[x].push_back(y);
G[y].push_back(x);
}

int main() {
freopen("maxflow.in", "r", stdin);
freopen("maxflow.out", "w", stdout);

scanf("%d %d", &n, &m);
S = 1, D = n;
for (int i = 1; i <= m; ++i) {
int x, y, c; scanf("%d %d %d", &x, &y, &c);
cap[x][y] = c;