# Cod sursa(job #2246671)

Utilizator Data 27 septembrie 2018 12:51:42 Flux maxim 60 cpp done Arhiva educationala 1.44 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
#define MAX 1010
#define INF 1000000000
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

typedef vector<int>::iterator iter;

int Cap[MAX][MAX], Flow[MAX][MAX];
vector<int> G[MAX], Gt[MAX];
queue<int> Q;
int dist[MAX], p[MAX];
int totalFlow = 0;
int bfs(int s, int d){
memset(dist, -1, sizeof(dist));
memset(p, 0, sizeof(p));
dist[s] = 0;
Q.push(s);
while(Q.size()) {
int node = Q.front();
Q.pop();
for(iter it = G[node].begin() ; it != G[node].end() ; it++) {
if(dist[*it] == -1 && Flow[node][*it] < Cap[node][*it]) {
dist[*it] = dist[node] + 1;
Q.push(*it);
p[*it] = node;
}
}
}
if(dist[d] == -1)
return 0;
int flux = INF;
for(int i = d ; i != s ; i = p[i]) {
flux = min(flux, Cap[p[i]][i] - Flow[p[i]][i]);
}
for(int i = d ; i != s ; i = p[i]) {
Flow[p[i]][i] += flux;
}
totalFlow += flux;
return flux;
}

int main(){
int n, m, i, j;
fin >> n >> m;

while(m--){
int x, y, c;
fin >> x >> y >> c;
G[x].push_back(y);
Gt[y].push_back(x);
Cap[x][y] = c;
Flow[x][y] = 0;
}

while(bfs(1, n)) {

}
fout << totalFlow << "\n";
}