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

#define apred u.A
#define res v.I
#define vertice w.V \

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

/*23:*/
#line 484 "aumentominimos.w"

/*24:*/
#line 496 "aumentominimos.w"

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

/*:24*/
#line 485 "aumentominimos.w"

/*14:*/
#line 291 "aumentominimos.w"

Vertex*ini,*fim,*zero;
Vertex*max;

void inicializa_fila(Graph*g){
ini= g->vertices;
fim= g->vertices;
zero= g->vertices;
max= g->vertices+g->n;
return;
}

void insere_fila(Vertex*i){
fim->vertice= i;
fim++;
if(fim> max){
fim= zero;
}
if(fim==ini){
fprintf(stderr,"ERRO: Fila excedeu sua capacidade.\n");
exit(-1);
}
}


boolean fila_vazia(){
if(ini==fim)
return TRUE;
return FALSE;
}

Vertex*remove_fila(){
Vertex*i;
if(!fila_vazia()){
i= ini->vertice;
ini++;
if(ini> max){
ini= zero;
}
return i;
}
return NULL;
}


Vertex*primeiro_fila(){
if(!fila_vazia()){
return ini->vertice;
}
return NULL;
}



/*:14*/
#line 486 "aumentominimos.w"

/*8:*/
#line 150 "aumentominimos.w"

int arco_original(Arc*a){
return(a->flx>=0);
}


/*:8*/
#line 487 "aumentominimos.w"

/*11:*/
#line 238 "aumentominimos.w"

long get_cap_residual(Arc*a){
if(!arco_original(a)){
return a->irmao->flx;
}
else{
return(a->cap-a->flx);
}
}


/*:11*/
#line 488 "aumentominimos.w"

/*5:*/
#line 100 "aumentominimos.w"

void caminhos_aumento_minimos(Graph*g,Vertex*s,Vertex*t){
/*13:*/
#line 270 "aumentominimos.w"

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


/*:13*/
#line 102 "aumentominimos.w"

/*6:*/
#line 121 "aumentominimos.w"

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


/*:6*/
#line 103 "aumentominimos.w"

/*7:*/
#line 133 "aumentominimos.w"

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


/*:7*/
#line 104 "aumentominimos.w"

iteracoes= 0;

/*9:*/
#line 177 "aumentominimos.w"

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

s->res= 0;

inicializa_fila(g);
insere_fila(s);

while(!fila_vazia()){
i= remove_fila();
/*10:*/
#line 215 "aumentominimos.w"

for(a= i->arcs;a;a= a->next){
j= a->tip;
if(j->apred==NULL&&j!=s){
cap_residual= get_cap_residual(a);
if(cap_residual> 0){
if(cap_residual<i->res||i==s){
j->res= cap_residual;
}
else{
j->res= i->res;
}
j->apred= a;
insere_fila(j);
}
}
}

/*:10*/
#line 189 "aumentominimos.w"

}





/*:9*/
#line 107 "aumentominimos.w"

while(t->apred!=NULL){
/*12:*/
#line 257 "aumentominimos.w"

a= t->apred;
while(a!=NULL){
if(!arco_original(a))
a->irmao->flx= a->irmao->flx-t->res;
else
a->flx= a->flx+t->res;
a= a->inicio->apred;
}


/*:12*/
#line 109 "aumentominimos.w"

/*9:*/
#line 177 "aumentominimos.w"

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

s->res= 0;

inicializa_fila(g);
insere_fila(s);

while(!fila_vazia()){
i= remove_fila();
/*10:*/
#line 215 "aumentominimos.w"

for(a= i->arcs;a;a= a->next){
j= a->tip;
if(j->apred==NULL&&j!=s){
cap_residual= get_cap_residual(a);
if(cap_residual> 0){
if(cap_residual<i->res||i==s){
j->res= cap_residual;
}
else{
j->res= i->res;
}
j->apred= a;
insere_fila(j);
}
}
}

/*:10*/
#line 189 "aumentominimos.w"

}





/*:9*/
#line 110 "aumentominimos.w"

iteracoes++;
}

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


/*:5*/
#line 489 "aumentominimos.w"

/*15:*/
#line 354 "aumentominimos.w"

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

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


/*:22*/
#line 358 "aumentominimos.w"

/*16:*/
#line 377 "aumentominimos.w"

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

if((g= restore_graph(argv[1]))==NULL){
fprintf(stderr,"ERRO: Problemas com arquivo de entrada.\n");
exit(-2);
}

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

/*:17*/
#line 382 "aumentominimos.w"

/*18:*/
#line 405 "aumentominimos.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,"ERRO: Vértices inválidos.\n");
exit(-4);
}

/*:18*/
#line 383 "aumentominimos.w"

/*19:*/
#line 421 "aumentominimos.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,"ERRO: Capacidade negativa encontrada.\n");
exit(-5);
}
}
}


/*:19*/
#line 384 "aumentominimos.w"


/*:16*/
#line 359 "aumentominimos.w"

caminhos_aumento_minimos(g,fonte,sorvedouro);
/*20:*/
#line 437 "aumentominimos.w"

for(max= 0,i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(arco_original(a)){
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);
fprintf(stdout,"Intensidade do fluxo máximo: %d\n",max);


/*:20*/
#line 361 "aumentominimos.w"

/*21:*/
#line 458 "aumentominimos.w"

fprintf(saida,"\nSeparador:\n");
for(min= 0,i= g->vertices;i<g->vertices+g->n;i++){
if(i->apred!=NULL||i==fonte){
fprintf(saida,"\"%s\"\n",i->name);
for(a= i->arcs;a;a= a->next){
if(arco_original(a)&&(a->tip->apred==NULL&&a->tip!=fonte))min+= a->cap;
}
}
}
fprintf(saida,"Capacidade: %d\n",min);
fprintf(stdout,"Capacidade do separador minimo: %d\n",min);
fclose(saida);

/*:21*/
#line 362 "aumentominimos.w"

return(0);
}


/*:15*/
#line 490 "aumentominimos.w"



/*:23*/