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

#define NAOVISTO 0
#define VISITADO 1 \

#define arcopred u.A
#define estado w.I
#define res x.I
#define prox y.V \

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

/*22:*/
#line 369 "capacityscaling.w"

/*23:*/
#line 378 "capacityscaling.w"

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

/*:23*/
#line 370 "capacityscaling.w"

/*13:*/
#line 208 "capacityscaling.w"

Vertex*head,*tail;

void inicializafila(){
head= NULL;
tail= NULL;
}

boolean filavazia(){
if(head==NULL)
return(TRUE);
return(FALSE);
}

Vertex*retiradafila(){
Vertex*i= head;
head= head->prox;
if(head==NULL)
tail= NULL;
return(i);
}

void inserenafila(Vertex*i){
if(head==NULL){
head= i;
tail= i;
}
else{
tail->prox= i;
tail= i;
}
i->prox= NULL;
return;
}

/*:13*/
#line 371 "capacityscaling.w"

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

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

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

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

/*6:*/
#line 97 "capacityscaling.w"

for(Delta= -1,i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(Delta<a->cap)Delta= a->cap;
}
}
fprintf(stdout,"capacidade máxima: %d\n",Delta);
Delta= (int)pow(2.0,floor(log((double)Delta)/log(2.0)));

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

/*7:*/
#line 108 "capacityscaling.w"

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

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

/*8:*/
#line 119 "capacityscaling.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;
}
}
}

/*:8*/
#line 80 "capacityscaling.w"

iteracoes= 0;
while(Delta>=1){
do{
/*9:*/
#line 138 "capacityscaling.w"

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

inicializafila();
inserenafila(fonte);
fonte->estado= VISITADO;

while(!filavazia()){
i= retiradafila();
/*10:*/
#line 162 "capacityscaling.w"

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

if(j->estado==NAOVISTO){
if(a->flx>=0)temp= a->cap-a->flx;
else temp= a->irmao->flx;
if(temp>=Delta){
if(i!=fonte&&temp> i->res)j->res= i->res;
else j->res= temp;
inserenafila(j);
j->estado= VISITADO;
j->arcopred= a;
}
}
}

/*:10*/
#line 150 "capacityscaling.w"

}

/*:9*/
#line 84 "capacityscaling.w"

/*11:*/
#line 186 "capacityscaling.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 85 "capacityscaling.w"

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

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

/*:5*/
#line 372 "capacityscaling.w"

/*14:*/
#line 251 "capacityscaling.w"

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

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

/*:21*/
#line 255 "capacityscaling.w"

/*15:*/
#line 272 "capacityscaling.w"

if(argc!=5){
fprintf(stderr,"%s <in> <out> \"source\" \"sink\"\n",argv[0]);
exit(-1);
}
/*16:*/
#line 285 "capacityscaling.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 277 "capacityscaling.w"

/*17:*/
#line 300 "capacityscaling.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 278 "capacityscaling.w"

/*18:*/
#line 316 "capacityscaling.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 279 "capacityscaling.w"


/*:15*/
#line 256 "capacityscaling.w"

capacityscaling(g,fonte,sorvedouro);
/*19:*/
#line 329 "capacityscaling.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 258 "capacityscaling.w"

/*20:*/
#line 345 "capacityscaling.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 259 "capacityscaling.w"

return(0);
}

/*:14*/
#line 373 "capacityscaling.w"


/*:22*/