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

#define dist u.I
#define exc v.I
#define prox w.V
#define atual x.A \

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

/*23:*/
#line 392 "excessscaling.w"

/*24:*/
#line 401 "excessscaling.w"

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

/*:24*/
#line 393 "excessscaling.w"

/*14:*/
#line 216 "excessscaling.w"

Vertex**lista;
int level,size;

void inicializalista(Graph*g){
int indice;
lista= (Vertex**)malloc((2*g->n)*sizeof(Vertex*));
for(indice= 0;indice<2*g->n;indice++)
lista[indice]= NULL;
level= 0;
size= 0;
return;
}

void finalizalista(){
free(lista);
return;
}

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

Vertex*retiradalista(){
Vertex*i;
while(lista[level]==NULL)level++;
i= lista[level];
lista[level]= i->prox;
size--;
return(i);
}

void inserenalista(Vertex*i){
i->prox= lista[i->dist];
lista[i->dist]= i;
if(i->dist<level)level= i->dist;
size++;
return;
}

/*:14*/
#line 394 "excessscaling.w"

/*5:*/
#line 71 "excessscaling.w"

void excessscaling(Graph*g,Vertex*fonte,Vertex*sorvedouro){
/*13:*/
#line 206 "excessscaling.w"

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

/*:13*/
#line 73 "excessscaling.w"

/*6:*/
#line 95 "excessscaling.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= Delta*g->m;
Delta= (int)pow(2.0,floor(log((double)Delta)/log(2.0)));

/*:6*/
#line 74 "excessscaling.w"

/*7:*/
#line 111 "excessscaling.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
i->dist= 0;
i->exc= 0;
i->atual= i->arcs;
}
for(i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(i==fonte&&a->tip!=fonte)a->flx= a->cap;
else a->flx= 0;
i->exc-= a->flx;
a->tip->exc+= a->flx;
}
}
fonte->dist= g->n;

/*:7*/
#line 75 "excessscaling.w"

/*8:*/
#line 131 "excessscaling.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 76 "excessscaling.w"

iteracoes= 0;
inicializalista(g);
while(Delta>=1){
/*9:*/
#line 147 "excessscaling.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
if(i!=sorvedouro&&i->exc> Delta/2)inserenalista(i);
}

/*:9*/
#line 80 "excessscaling.w"

while(!listavazia()){
i= retiradalista();
/*10:*/
#line 156 "excessscaling.w"

for(a= i->atual;a;a= a->next){
if(a->flx>=0)temp= a->cap-a->flx;
else temp= a->irmao->flx;
if(temp> 0&&i->dist==a->tip->dist+1)break;
}
if(a==NULL){
/*11:*/
#line 178 "excessscaling.w"

for(min= -1,a= i->arcs;a;a= a->next){
if(a->flx>=0)temp= a->cap-a->flx;
else temp= a->irmao->flx;
if(temp> 0&&a->tip!=i){
if(min==-1||min> a->tip->dist)min= a->tip->dist;
}
}
i->dist= min+1;
inserenalista(i);

/*:11*/
#line 163 "excessscaling.w"

i->atual= i->arcs;
}
else{
/*12:*/
#line 192 "excessscaling.w"

if(i->exc<temp)temp= i->exc;
if(a->tip!=sorvedouro&&Delta-a->tip->exc<temp)temp= Delta-a->tip->exc;
if(a->flx>=0)a->flx+= temp;
else a->irmao->flx-= temp;
i->exc-= temp;
a->tip->exc+= temp;
if(i->exc> Delta/2)inserenalista(i);
if(a->tip!=sorvedouro&&a->tip->exc> Delta/2){
if(a->tip->exc-temp<=Delta/2)inserenalista(a->tip);
}

/*:12*/
#line 167 "excessscaling.w"

i->atual= a;
}

/*:10*/
#line 83 "excessscaling.w"

iteracoes++;
}
Delta= Delta/2;
}
finalizalista();
fprintf(stdout,"número de iterações: %d\n",iteracoes);
return;
}

/*:5*/
#line 395 "excessscaling.w"

/*15:*/
#line 266 "excessscaling.w"

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

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

/*:22*/
#line 270 "excessscaling.w"

/*16:*/
#line 287 "excessscaling.w"

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

/*:17*/
#line 292 "excessscaling.w"

/*18:*/
#line 315 "excessscaling.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);
}

/*:18*/
#line 293 "excessscaling.w"

/*19:*/
#line 331 "excessscaling.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);
}
}
}

/*:19*/
#line 294 "excessscaling.w"


/*:16*/
#line 271 "excessscaling.w"

excessscaling(g,fonte,sorvedouro);
/*20:*/
#line 344 "excessscaling.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",a->inicio->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);

/*:20*/
#line 273 "excessscaling.w"

/*21:*/
#line 361 "excessscaling.w"

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

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

/*:21*/
#line 274 "excessscaling.w"

return(0);
}

/*:15*/
#line 396 "excessscaling.w"


/*:23*/