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

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

#define demanda u.I
#define dist v.I
#define exc w.I
#define atual x.A
#define arcopred x.A
#define prox y.V
#define heapindex y.I
#define estado z.I \

#define cap len
#define custo a.I
#define est b.I
#define flx(a) ((struct str_arc*) a->b.I) ->f
#define irmao(a) ((struct str_arc*) a->b.I) ->i
#define novo(a) ((struct str_arc*) a->b.I) ->n
#define inicio(a) ((struct str_arc*) a->b.I) ->i->tip \

/*33:*/
#line 726 "pathscaling.w"

/*34:*/
#line 737 "pathscaling.w"

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

/*:34*/
#line 727 "pathscaling.w"

/*36:*/
#line 776 "pathscaling.w"

struct str_arc{
int f;
Arc*i;
boolean n;
};

/*:36*/
#line 728 "pathscaling.w"

int*potencial;
/*25:*/
#line 520 "pathscaling.w"

Vertex**heap;
int heapsize;

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]->heapindex= k1;
heap[k2]->heapindex= k2;
return;
}

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

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

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

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

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

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

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

/*:25*/
#line 730 "pathscaling.w"

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

void pathscaling(Graph*g){
/*24:*/
#line 507 "pathscaling.w"

Graph*h;
Vertex**lista;
Arc*a,*final,*arctemp;
Vertex*i,*j,*k,*fonte,*sorvedouro,*excesso,*deficit;
int iteracoes,temp,min,level,size,indice,capalta,custalto,max,ddp,Delta;

/*:24*/
#line 77 "pathscaling.w"

/*6:*/
#line 108 "pathscaling.w"

/*7:*/
#line 119 "pathscaling.w"

h= gb_new_graph(g->n+2);
fonte= h->vertices+g->n;
sorvedouro= h->vertices+g->n+1;

for(i= h->vertices,j= g->vertices;j<g->vertices+g->n;i++,j++){
i->name= j->name;
if(j->demanda<0)gb_new_arc(fonte,i,-j->demanda);
else gb_new_arc(i,sorvedouro,j->demanda);

final= NULL;
for(a= j->arcs;a;a= a->next)final= a;
while(final){
k= h->vertices+(final->tip-g->vertices);
gb_new_arc(i,k,final->cap);
if(j->arcs==final)final= NULL;
else{
for(a= j->arcs;a!=final;a= a->next)arctemp= a;
final= arctemp;
}
}
}

/*:7*/
#line 109 "pathscaling.w"

/*8:*/
#line 146 "pathscaling.w"

for(i= h->vertices;i<h->vertices+h->n;i++){
i->dist= 0;
i->exc= 0;
i->atual= i->arcs;
}
for(i= h->vertices;i<h->vertices+h->n;i++){
for(a= i->arcs;a;a= a->next){
a->est= (int)malloc(sizeof(struct str_arc));
if(i==fonte&&a->tip!=fonte)flx(a)= a->cap;
else flx(a)= 0;
i->exc-= flx(a);
a->tip->exc+= flx(a);
}
}
fonte->dist= h->n;

for(i= h->vertices;i<h->vertices+h->n;i++){
for(a= i->arcs;a;a= a->next){
if(flx(a)>=0){
j= a->tip;
gb_new_arc(j,i,a->cap);
irmao(a)= j->arcs;
irmao(a)->est= (int)malloc(sizeof(struct str_arc));
flx(irmao(a))= -1;
irmao(irmao(a))= a;
}
}
}

lista= (Vertex**)malloc((2*h->n)*sizeof(Vertex*));
for(indice= 0;indice<2*h->n;indice++)
lista[indice]= NULL;
level= 0;
size= 0;

for(i= h->vertices;i<h->vertices+h->n;i++){
if(i!=sorvedouro&&i->exc> 0){
i->prox= lista[i->dist];
lista[i->dist]= i;
if(i->dist> level)level= i->dist;
size++;
}
}

while(size> 0){

while(lista[level]==NULL)level--;
i= lista[level];
lista[level]= i->prox;
size--;

for(a= i->atual;a;a= a->next){
if(flx(a)>=0)temp= a->cap-flx(a);
else temp= flx(irmao(a));
if(temp> 0&&i->dist==a->tip->dist+1)break;
}
if(a==NULL){

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

i->prox= lista[i->dist];
lista[i->dist]= i;
if(i->dist> level)level= i->dist;
size++;

i->atual= i->arcs;
}
else{

if(i->exc<temp)temp= i->exc;
if(flx(a)>=0)flx(a)+= temp;
else flx(irmao(a))-= temp;
i->exc-= temp;
a->tip->exc+= temp;
if(i->exc> 0){

i->prox= lista[i->dist];
lista[i->dist]= i;
if(i->dist> level)level= i->dist;
size++;

}
if(a->tip!=sorvedouro&&a->tip->exc> 0){
if(a->tip->exc-temp==0){

a->tip->prox= lista[a->tip->dist];
lista[a->tip->dist]= a->tip;
if(a->tip->dist> level)level= a->tip->dist;
size++;

}
}
i->atual= a;
}

}
free(lista);

/*:8*/
#line 110 "pathscaling.w"

/*9:*/
#line 257 "pathscaling.w"

for(i= h->vertices;i<h->vertices+h->n;i++){
for(a= i->arcs;a;a= a->next){
if(i==fonte||a->tip==sorvedouro){
if(flx(a)>=0&&flx(a)<a->cap){
fprintf(stderr,"problema inviável\n");
exit(0);
}
}
}
}

/*:9*/
#line 111 "pathscaling.w"


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

/*10:*/
#line 271 "pathscaling.w"

for(Delta= -1,i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(a->custo>=0){
if(Delta<a->custo)Delta= a->custo;
}
if(a->custo<0){
if(Delta<-a->custo)Delta= -a->custo;
}
}
}
fprintf(stdout,"custo máximo: %d\n",Delta);
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)));

/*:10*/
#line 79 "pathscaling.w"

/*11:*/
#line 297 "pathscaling.w"

/*12:*/
#line 321 "pathscaling.w"

for(max= -1,i= g->vertices;i<g->vertices+g->n;i++){
if(i->demanda>=0){
if(max<i->demanda)max= i->demanda;
}
else{
if(max<-i->demanda)max= -i->demanda;
}
}
capalta= (max*g->n)+Delta;

/*:12*/
#line 298 "pathscaling.w"

/*13:*/
#line 334 "pathscaling.w"

for(max= -1,i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(max<a->custo)max= a->custo;
}
}
custalto= max*g->m;

/*:13*/
#line 299 "pathscaling.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
a->est= (int)malloc(sizeof(struct str_arc));
novo(a)= FALSE;
}
}
for(i= g->vertices+1;i<g->vertices+g->n;i++){
gb_new_arc(g->vertices,i,capalta);
g->vertices->arcs->custo= custalto;
g->vertices->arcs->est= (int)malloc(sizeof(struct str_arc));
novo(g->vertices->arcs)= TRUE;
gb_new_arc(i,g->vertices,capalta);
i->arcs->custo= custalto;
i->arcs->est= (int)malloc(sizeof(struct str_arc));
novo(i->arcs)= TRUE;
}

/*:11*/
#line 80 "pathscaling.w"

/*14:*/
#line 346 "pathscaling.w"

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

/*:14*/
#line 81 "pathscaling.w"

/*15:*/
#line 362 "pathscaling.w"

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

/*:15*/
#line 82 "pathscaling.w"

/*16:*/
#line 379 "pathscaling.w"

potencial= (int*)malloc(g->n*sizeof(int));
for(indice= 0;indice<g->n;indice++){
potencial[indice]= 0;
}

/*:16*/
#line 83 "pathscaling.w"
;

iteracoes= 0;
while(Delta>=1){
/*18:*/
#line 407 "pathscaling.w"

excesso= NULL;
deficit= NULL;
for(i= g->vertices;i<g->vertices+g->n;i++){
if(i->exc-i->demanda>=Delta)excesso= i;
if(i->exc-i->demanda<=-Delta)deficit= i;
if(excesso!=NULL&&deficit!=NULL)break;
}

/*:18*/
#line 87 "pathscaling.w"

while(excesso!=NULL&&deficit!=NULL){
/*19:*/
#line 424 "pathscaling.w"

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

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

while(!filavazia()){
i= retiradafila();
i->estado= EXAMINADO;
/*20:*/
#line 449 "pathscaling.w"

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

if(j->estado!=EXAMINADO){
if(flx(a)>=0)temp= a->cap-flx(a);
else temp= flx(irmao(a));
if(temp>=Delta){
/*21:*/
#line 468 "pathscaling.w"

ddp= potencial[i-g->vertices]-potencial[j-g->vertices];
temp= i->dist+a->custo-ddp;
if(j->estado==NAOVISTO){
inserenafila(j,temp);
j->estado= VISITADO;
j->arcopred= a;
}
else if(temp<j->dist){
reinserenafila(j,temp);
j->arcopred= a;
}

/*:21*/
#line 457 "pathscaling.w"

}
}
}

/*:20*/
#line 437 "pathscaling.w"

}

finalizafila();

/*:19*/
#line 89 "pathscaling.w"

/*22:*/
#line 484 "pathscaling.w"

for(indice= 0;indice<g->n;indice++)
potencial[indice]-= (g->vertices+indice)->dist;

/*:22*/
#line 90 "pathscaling.w"

/*23:*/
#line 494 "pathscaling.w"

a= deficit->arcopred;
while(a!=NULL){
if(flx(a)>=0)flx(a)+= Delta;
else flx(irmao(a))-= Delta;
inicio(a)->exc-= Delta;
a->tip->exc+= Delta;
if(inicio(a)==fonte)a= NULL;
else a= inicio(a)->arcopred;
}

/*:23*/
#line 91 "pathscaling.w"

/*18:*/
#line 407 "pathscaling.w"

excesso= NULL;
deficit= NULL;
for(i= g->vertices;i<g->vertices+g->n;i++){
if(i->exc-i->demanda>=Delta)excesso= i;
if(i->exc-i->demanda<=-Delta)deficit= i;
if(excesso!=NULL&&deficit!=NULL)break;
}

/*:18*/
#line 92 "pathscaling.w"

iteracoes++;
}
/*17:*/
#line 390 "pathscaling.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(flx(a)>=0)temp= a->cap-flx(a);
else temp= flx(irmao(a));
ddp= potencial[i-g->vertices]-potencial[a->tip-g->vertices];
if(temp>=Delta/2&&a->custo-ddp<0){
if(flx(a)>=0)flx(a)+= temp;
else flx(irmao(a))-= temp;
i->exc-= temp;
a->tip->exc+= temp;
}
}
}

/*:17*/
#line 95 "pathscaling.w"

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

/*:5*/
#line 731 "pathscaling.w"

/*26:*/
#line 617 "pathscaling.w"

int main(int argc,char*argv[]){
Graph*g;
/*32:*/
#line 717 "pathscaling.w"

Arc*a;
Vertex*i;
FILE*saida;
int min,ddp,temp;

/*:32*/
#line 620 "pathscaling.w"

/*27:*/
#line 637 "pathscaling.w"

if(argc!=3){
fprintf(stderr,"%s <in> <out>\n",argv[0]);
exit(-1);
}
/*28:*/
#line 649 "pathscaling.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);
}

/*:28*/
#line 642 "pathscaling.w"

/*29:*/
#line 664 "pathscaling.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);
}
}
}

/*:29*/
#line 643 "pathscaling.w"


/*:27*/
#line 621 "pathscaling.w"

pathscaling(g);
/*30:*/
#line 678 "pathscaling.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
fprintf(saida,"\"%s\": demanda %ld e excesso %ld\n",i->name,i->demanda,i->exc);
}
for(min= 0,i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(flx(a)>=0&&novo(a)==FALSE){
fprintf(saida,"fluxo de \"%s\" a \"%s\": %d\n",i->name,a->tip->name,flx(a));
min+= flx(a)*a->custo;
}
}
}
fprintf(saida,"custo: %d\n",min);

/*:30*/
#line 623 "pathscaling.w"

/*31:*/
#line 696 "pathscaling.w"

fprintf(saida,"custos reduzidos:\n");
for(min= 0,i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(flx(a)>=0)temp= a->cap-flx(a);
else temp= flx(irmao(a));
if(flx(a)>=0&&temp> 0&&novo(a)==FALSE){
ddp= potencial[i-g->vertices]-potencial[a->tip-g->vertices];
fprintf(saida,"custo reduzido de \"%s\" a \"%s\": %ld\n",
i->name,a->tip->name,a->custo-ddp);
}
if(flx(a)<0&&temp> 0&&novo(irmao(a))==FALSE){
ddp= potencial[i-g->vertices]-potencial[a->tip-g->vertices];
fprintf(saida,"custo reduzido de \"%s\" a \"%s\": %ld\n",
i->name,a->tip->name,a->custo-ddp);
}
}
}

/*:31*/
#line 624 "pathscaling.w"

return(0);
}

/*:26*/
#line 732 "pathscaling.w"


/*:33*/