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

#define dist u.I
#define vertice v.V \

#define cap len
#define pos a.I
#define irmao b.A
#define inicio irmao->tip
#define flx_bloq(a) flx_bloq[a->pos]
#define flx(a) flx[a->pos] \
 \

/*36:*/
#line 697 "flxbloq.w"

/*38:*/
#line 719 "flxbloq.w"

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

/*:38*/
#line 698 "flxbloq.w"

/*37:*/
#line 713 "flxbloq.w"

long*flx,*flx_bloq;

/*:37*/
#line 699 "flxbloq.w"

/*25:*/
#line 466 "flxbloq.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;
}



/*:25*/
#line 700 "flxbloq.w"

/*21:*/
#line 405 "flxbloq.w"

long min(long a,long b){
if(a> b){
return b;
}
return a;
}


/*:21*/
#line 701 "flxbloq.w"

/*10:*/
#line 208 "flxbloq.w"

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


/*:10*/
#line 702 "flxbloq.w"

/*15:*/
#line 302 "flxbloq.w"

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


/*:15*/
#line 703 "flxbloq.w"

/*19:*/
#line 370 "flxbloq.w"

long envia_fluxo_bloqueador(Vertex*i,Vertex*t,long fluxo){
/*22:*/
#line 416 "flxbloq.w"

Vertex*j;
Arc*a;
long flx_sobra;
long flx_caminho;



/*:22*/
#line 372 "flxbloq.w"


flx_sobra= fluxo;

if(i==t){
return fluxo;
}

for(a= i->arcs;a&&flx_sobra> 0;a= a->next){
if(get_cap_residual(a)> 0){
j= a->tip;
if(j->dist==i->dist+1){
/*20:*/
#line 396 "flxbloq.w"

if(flx_bloq(a)<get_cap_residual(a)){
flx_caminho= envia_fluxo_bloqueador(j,t,min(flx_sobra,(get_cap_residual(a)-flx_bloq(a))));
flx_bloq(a)+= flx_caminho;
flx_sobra-= flx_caminho;
}

/*:20*/
#line 384 "flxbloq.w"

}
}
}
return(fluxo-flx_sobra);
}


/*:19*/
#line 704 "flxbloq.w"

/*14:*/
#line 279 "flxbloq.w"

void busca_em_profundidade(Vertex*i){
Vertex*j;
Arc*a;

for(a= i->arcs;a;a= a->next){
if(get_cap_residual(a)> 0){
j= a->tip;
if(j->dist==-1){
j->dist= i->dist+1;
busca_em_profundidade(j);
}
}
}
return;
}


/*:14*/
#line 705 "flxbloq.w"

/*6:*/
#line 131 "flxbloq.w"

void fluxos_bloqueadores_aumento(Graph*g,Vertex*s,Vertex*t,boolean largura){
/*24:*/
#line 446 "flxbloq.w"

long iteracoes,indice,max_fluxo;
Vertex*i,*j;
Arc*a;

/*:24*/
#line 133 "flxbloq.w"

/*7:*/
#line 166 "flxbloq.w"

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


/*:7*/
#line 134 "flxbloq.w"

/*8:*/
#line 177 "flxbloq.w"

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


/*:8*/
#line 135 "flxbloq.w"

/*9:*/
#line 189 "flxbloq.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->irmao= a;
a->irmao->pos= indice++;
flx(a->irmao)= -1;
}
}
}



/*:9*/
#line 136 "flxbloq.w"

iteracoes= 0;

do{
if(largura){
/*12:*/
#line 241 "flxbloq.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
i->dist= -1;
}

s->dist= 0;
inicializa_fila(g);
insere_fila(s);

while(!fila_vazia()){
i= remove_fila();

for(a= i->arcs;a;a= a->next){
if(get_cap_residual(a)> 0){
j= a->tip;
if(j->dist==-1){
j->dist= i->dist+1;
insere_fila(j);
}
}
}
}


/*:12*/
#line 141 "flxbloq.w"

}
else{
/*13:*/
#line 267 "flxbloq.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
i->dist= -1;
}

s->dist= 0;
busca_em_profundidade(s);


/*:13*/
#line 144 "flxbloq.w"

}
if(t->dist!=-1){
/*16:*/
#line 324 "flxbloq.w"

/*17:*/
#line 334 "flxbloq.w"

max_fluxo= 0;
for(a= s->arcs;a;a= a->next){
if(a->tip->dist==s->dist+1)
max_fluxo+= get_cap_residual(a);
}


/*:17*/
#line 325 "flxbloq.w"

/*18:*/
#line 345 "flxbloq.w"

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


/*:18*/
#line 326 "flxbloq.w"

envia_fluxo_bloqueador(s,t,max_fluxo);


/*:16*/
#line 147 "flxbloq.w"

/*23:*/
#line 431 "flxbloq.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(!arco_original(a)){
flx(a->irmao)-= flx_bloq(a);
}
else{
flx(a)+= flx_bloq(a);
}
}
}


/*:23*/
#line 148 "flxbloq.w"

iteracoes++;
}
}while(t->dist!=-1);


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


/*:6*/
#line 706 "flxbloq.w"

/*26:*/
#line 530 "flxbloq.w"

int main(int argc,char*argv[]){
Graph*g;
Vertex*fonte,*sorvedouro;
boolean largura;
/*35:*/
#line 687 "flxbloq.w"

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


/*:35*/
#line 535 "flxbloq.w"

/*28:*/
#line 572 "flxbloq.w"

if(argc!=5&&argc!=6){
fprintf(stderr,"Uso: %s <in> <out> \"source\" \"sink\" [-p]\n",argv[0]);

exit(-1);
}
/*29:*/
#line 587 "flxbloq.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);
}

/*:29*/
#line 578 "flxbloq.w"

/*30:*/
#line 602 "flxbloq.w"

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

/*:30*/
#line 579 "flxbloq.w"

/*31:*/
#line 618 "flxbloq.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);
}
}
}

/*:31*/
#line 580 "flxbloq.w"

/*32:*/
#line 634 "flxbloq.w"

largura= TRUE;
if(argc==6){
if(strcmp("-p",argv[5])==0)largura= FALSE;
else{
fprintf(stderr,"ERRO: Opção inválida: %s.\n",argv[5]);
exit(-6);
}
}


/*:32*/
#line 581 "flxbloq.w"


/*:28*/
#line 536 "flxbloq.w"

/*27:*/
#line 551 "flxbloq.w"

flx= (long*)malloc(2*g->m*sizeof(long));
flx_bloq= (long*)malloc(2*g->m*sizeof(long));

if(!flx||!flx_bloq){
fprintf(stderr,"ERRO: Problemas com alocação de memória.\n");
exit(-1);
}

/*:27*/
#line 537 "flxbloq.w"

fluxos_bloqueadores_aumento(g,fonte,sorvedouro,largura);
/*33:*/
#line 650 "flxbloq.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,flx(a));
if(i==sorvedouro)max-= flx(a);
if(a->tip==sorvedouro)max+= flx(a);
}
}
}
fprintf(saida,"Intensidade: %d\n",max);
fprintf(stdout,"Intensidade do fluxo máximo: %d\n",max);


/*:33*/
#line 539 "flxbloq.w"

/*34:*/
#line 671 "flxbloq.w"

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

/*:34*/
#line 540 "flxbloq.w"

return(0);
}

/*:26*/
#line 707 "flxbloq.w"



/*:36*/