# Cod sursa(job #2246686)

Utilizator Data 27 septembrie 2018 13:07:44 Flux maxim 10 cpp done Arhiva educationala 1.68 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];
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;

for(iter it = G[d].begin() ; it != G[d].end() ; it++) {
p[d] = *it;
int flux = INF;
if(dist[p[d]] == -1 || Cap[p[d]][d] == Flow[p[d]][d])
continue;
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;
Flow[i][p[i]] -= flux;
}

totalFlow += flux;
}

return 1;
}

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);
G[y].push_back(x);
Cap[x][y] = c;
Flow[x][y] = 0;
}

while(bfs(1, n)) {

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