Cod sursa(job #2120675)

Utilizator Data 2 februarie 2018 19:14:54 Flux maxim 70 cpp done Arhiva educationala 2.39 kb
``````#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

struct graf{
int nod;
graf* next;
};

int n;

graf* g[1001];
int res[1001][1001];

int flow;
int c[1001];
int q[1001];
int a,b;
int tati[1001];
int dist[1001];

void add(int a, int b, graf* v[])
{
graf* q = new graf;
q->nod  = b;
q->next = v[a];
v[a] = q;
}

void BFS(int k,int d){
graf*  p;
for(p = g[k]; p!=NULL; p=p->next){
if(c[p->nod] == 0 && res[p->nod][k] > 0){
++b;
q[b] = p->nod;
c[p->nod] = 1;
dist[p->nod] = d + 1;
}
}
++a;

if(b >= a)
BFS(q[a],dist[q[a]]);
}

void augment(int k){
int x = k;
int minim = 100200;

while(x != 1){
if(minim > res[tati[x]][x])
minim = res[tati[x]][x];
x = tati[x];
}
flow = flow + minim;

x = k;
while(x != 1){
res[tati[x]][x] = res[tati[x]][x] - minim;
res[x][tati[x]] = res[x][tati[x]] + minim;
x = tati[x];
}
}

void update(){

int x = n;
int minim = 100200;

augment(n);

}

int main()
{
int m,x,y,z,i,j;
fin >> n >> m;
for(i=1;i<=m;++i){
fin >> x >> y >> z;
res[x][y] = z;
}

c[n] = 1;
for(i=1;i<=n-1;++i)
c[i] = 0;
a = b = 0;
q[0] = n;

BFS(n,0);
int current = 1;
int aux;
bool liar = 1;

while(dist[1] < n){
graf*  p;
aux = 1002;
liar = 1;
for(p = g[current]; p!=NULL; p=p->next){
if(dist[p->nod]<aux && res[current][p->nod])
aux = dist[p->nod];

if(dist[p->nod] + 1 == dist[current] && res[current][p->nod]){
liar = 0;
tati[p->nod] = current;
current = p->nod;
if(current == n){
augment(n);
current = 1;
}
break;
}
}

if(liar){
dist[current] = aux + 1;
if(current != 1)
current = tati[current];
}
}

fout << flow;

return 0;
}
``````