Pagini recente » Cod sursa (job #1613123) | Cod sursa (job #1914475) | Istoria paginii runda/pregatireoji/clasament | Cod sursa (job #772070) | Cod sursa (job #318508)
Cod sursa(job #318508)
#include <stdio.h>
#include <math.h>
#define INF 2000000000
long n, m, a, b, c, i, C[1024][1024], flux[1024], up[1024], total, Q[1024];
inline long min(long a, long b) {if (a > b) return b; return a;}
void fill(long *v, long cat) {
for (i = 1; i <= n; ++i) v[i] = cat;
}
long bfs() {
fill(flux, 0);
flux[1] = INF;
fill(up, -1);
Q[0] = 1;
long l, r, crt;
for (l = r = 0; l <= r; ++l) {
crt = Q[l];
for (long nxt = 1; nxt <= n; ++nxt) {
if (C[crt][nxt] != 0 && flux[nxt] == 0) {
Q[++r] = nxt;
up[nxt] = crt;
flux[nxt] = min(C[crt][nxt], flux[crt]);
}
}
}
if (flux[n] == 0) {
return 0;
}
total += flux[n];
for (long nod = n; nod >= 2; nod = up[nod]) {
C[nod][up[nod]] += flux[n];
C[up[nod]][nod] -= flux[n];
}
return 1;
}
int main() {
freopen("maxflow.in", "r", stdin);
freopen("maxflow.out", "w", stdout);
scanf("%ld %ld", &n, &m);
for (i = 1; i <= m; ++i) {
scanf("%ld %ld %ld", &a, &b, &c);
C[a][b] = c;
C[b][a] = 0;
}
while(bfs());
printf("%ld\n", total);
return 0;
}