#define boolean int
#define FALSE 0
#define TRUE 1 \

#define NAOVISTO 0
#define VISITADO 1
#define EXAMINADO 2 \

#define arcopred u.A
#define res v.I
#define estado w.I
#define indice x.I \

#define cap len
#define flx a.I
#define irmao b.A
#define inicio irmao->tip \

/*22:*/
#line 431 "maioraumento.w"

/*23:*/
#line 440 "maioraumento.w"

#include <stdio.h>  
#include <stdlib.h>  
#include <gb_graph.h>  
#include <gb_save.h>  

/*:23*/
#line 432 "maioraumento.w"

/*13:*/
#line 216 "maioraumento.w"

Vertex**heap;
int size;

int parent(int k){
return(k/2);
}

int left(int k){
return(2*k);
}

int right(int k){
return((2*k)+1);
}

void exchange(int k1,int k2){
Vertex*i;
i= heap[k1];
heap[k1]= heap[k2];
heap[k2]= i;
heap[k1]->indice= k1;
heap[k2]->indice= k2;
return;
}

void heapify(int k){
int l,r,maior;
l= left(k);
r= right(k);
if(l<=size&&heap[l]->res> heap[k]->res)
maior= l;
else
maior= k;
if(r<=size&&heap[r]->res> heap[maior]->res)
maior= r;
if(maior!=k){
exchange(k,maior);
heapify(maior);
}
return;
}

void inicializafila(Graph*g){
heap= (Vertex**)malloc((g->n+1)*sizeof(Vertex*));
size= 0;
return;
}

void finalizafila(){
free(heap);
return;
}

boolean filavazia(){
if(size==0)
return(TRUE);
return(FALSE);
}

Vertex*retiradafila(){
Vertex*i;
i= heap[1];
heap[1]= heap[size];
heap[1]->indice= 1;
size--;
heapify(1);
return(i);
}

void reinserenafila(Vertex*i,int key){
int k;
k= i->indice;
i->res= key;
while(k> 1&&heap[parent(k)]->res<heap[k]->res){
exchange(k,parent(k));
k= parent(k);
}
return;
}

void inserenafila(Vertex*i,int key){
size++;
heap[size]= i;
i->indice= size;
reinserenafila(i,key);
return;
}

/*:13*/
#line 433 "maioraumento.w"

/*5:*/
#line 75 "maioraumento.w"

void maioraumento(Graph*g,Vertex*fonte,Vertex*sorvedouro){
/*12:*/
#line 204 "maioraumento.w"

int iteracoes,temp;
Vertex*i,*j;
Arc*a;

/*:12*/
#line 77 "maioraumento.w"

/*6:*/
#line 94 "maioraumento.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
a->flx= 0;
}
}

/*:6*/
#line 78 "maioraumento.w"

/*7:*/
#line 105 "maioraumento.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(a->flx>=0){
j= a->tip;
gb_new_arc(j,i,a->cap);
a->irmao= j->arcs;
a->irmao->flx= -1;
a->irmao->irmao= a;
}
}
}

/*:7*/
#line 79 "maioraumento.w"

iteracoes= 0;

do{
/*8:*/
#line 128 "maioraumento.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
i->arcopred= NULL;
i->estado= NAOVISTO;
}

inicializafila(g);
inserenafila(fonte,0);
fonte->estado= VISITADO;

while(!filavazia()){
i= retiradafila();
i->estado= EXAMINADO;
/*9:*/
#line 153 "maioraumento.w"

for(a= i->arcs;a;a= a->next){
j= a->tip;

if(j->estado!=EXAMINADO){
if(a->flx>=0)temp= a->cap-a->flx;
else temp= a->irmao->flx;
if(temp> 0){
/*10:*/
#line 172 "maioraumento.w"

if(i!=fonte&&temp> i->res){
temp= i->res;
}
if(j->estado==NAOVISTO){
inserenafila(j,temp);
j->estado= VISITADO;
j->arcopred= a;
}
else if(temp> j->res){
reinserenafila(j,temp);
j->arcopred= a;
}

/*:10*/
#line 161 "maioraumento.w"

}
}
}

/*:9*/
#line 141 "maioraumento.w"

}

finalizafila();

/*:8*/
#line 83 "maioraumento.w"

/*11:*/
#line 193 "maioraumento.w"

a= sorvedouro->arcopred;
while(a!=NULL){
if(a->flx>=0)a->flx= a->flx+sorvedouro->res;
else a->irmao->flx= a->irmao->flx-sorvedouro->res;
if(a->inicio==fonte)a= NULL;
else a= a->inicio->arcopred;
}

/*:11*/
#line 84 "maioraumento.w"

iteracoes++;
}while(sorvedouro->arcopred!=NULL);

fprintf(stdout,"número de iterações: %d\n",iteracoes-1);
return;
}

/*:5*/
#line 434 "maioraumento.w"

/*14:*/
#line 313 "maioraumento.w"

int main(int argc,char*argv[]){
Graph*g;
Vertex*fonte,*sorvedouro;
/*21:*/
#line 422 "maioraumento.w"

Vertex*i;
Arc*a;
int min,max;
FILE*saida;

/*:21*/
#line 317 "maioraumento.w"

/*15:*/
#line 334 "maioraumento.w"

if(argc!=5){
fprintf(stderr,"%s <in> <out> \"source\" \"sink\"\n",argv[0]);
exit(-1);
}
/*16:*/
#line 347 "maioraumento.w"

if((g= restore_graph(argv[1]))==NULL){
fprintf(stderr,"entrada inválida\n");
exit(-2);
}

if((saida= fopen(argv[2],"w"))==NULL){
fprintf(stderr,"saída inválida\n");
exit(-3);
}

/*:16*/
#line 339 "maioraumento.w"

/*17:*/
#line 362 "maioraumento.w"

fonte= NULL;
sorvedouro= NULL;
for(i= g->vertices;i<g->vertices+g->n;i++){
if(!strcmp(i->name,argv[3]))fonte= i;
if(!strcmp(i->name,argv[4]))sorvedouro= i;
}
if(fonte==NULL||sorvedouro==NULL){
fprintf(stderr,"vértices inválidos\n");
exit(-4);
}

/*:17*/
#line 340 "maioraumento.w"

/*18:*/
#line 378 "maioraumento.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(a->cap<0){
fprintf(stderr,"capacidades negativas\n");
exit(-5);
}
}
}

/*:18*/
#line 341 "maioraumento.w"


/*:15*/
#line 318 "maioraumento.w"

maioraumento(g,fonte,sorvedouro);
/*19:*/
#line 391 "maioraumento.w"

for(max= 0,i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(a->flx>=0){
fprintf(saida,"fluxo de \"%s\" a \"%s\": %ld\n",i->name,a->tip->name,a->flx);
if(i==sorvedouro)max-= a->flx;
if(a->tip==sorvedouro)max+= a->flx;
}
}
}
fprintf(saida,"intensidade: %d\n",max);

/*:19*/
#line 320 "maioraumento.w"

/*20:*/
#line 407 "maioraumento.w"

fprintf(saida,"separador:\n");
for(min= 0,i= g->vertices;i<g->vertices+g->n;i++){
if(i->estado!=NAOVISTO){
fprintf(saida,"\"%s\"\n",i->name);
for(a= i->arcs;a;a= a->next){
if(a->flx>=0&&a->tip->estado==NAOVISTO)min+= a->cap;
}
}
}
fprintf(saida,"capacidade: %d\n",min);
fclose(saida);

/*:20*/
#line 321 "maioraumento.w"

return(0);
}

/*:14*/
#line 435 "maioraumento.w"


/*:22*/