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

#define demanda u.I
#define exc v.I
#define res v.I
#define pos w.I
#define apred x.A
#define atual y.A
#define vertice z.V
#define potencial(i) potencial[i->pos] \

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

/*30:*/
#line 719 "costscaling.w"

/*31:*/
#line 732 "costscaling.w"

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


/*:31*/
#line 720 "costscaling.w"

/*33:*/
#line 767 "costscaling.w"

double*potencial;

struct str_arc{
long flx;
Arc*irmao;
};

/*:33*/
#line 721 "costscaling.w"

/*22:*/
#line 534 "costscaling.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;
}




/*:22*/
#line 722 "costscaling.w"

/*12:*/
#line 327 "costscaling.w"

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


/*:12*/
#line 723 "costscaling.w"

/*13:*/
#line 338 "costscaling.w"

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


/*:13*/
#line 724 "costscaling.w"

/*5:*/
#line 89 "costscaling.w"

void costscaling(Graph*g){
/*21:*/
#line 510 "costscaling.w"

int iteracoes,indice;
long max_custo,c,cap_residual,alpha;
double custo_reduzido,epsilon;
boolean viavel;
Vertex*i,*j,*s,*t;
Arc*a,*aux;
void*temp;



/*:21*/
#line 91 "costscaling.w"

/*6:*/
#line 118 "costscaling.w"

potencial= (double*)malloc(g->n*sizeof(double));
indice= 0;
for(i= g->vertices;i<g->vertices+g->n;i++){
i->pos= indice++;
for(a= i->arcs;a;a= a->next){
temp= malloc(sizeof(struct str_arc));
if(temp==NULL){
fprintf(stderr,"ERRO: Problemas com alocação de memória.\n");
exit(-1);
}
a->est= (int)temp;
}
}


/*:6*/
#line 92 "costscaling.w"

/*7:*/
#line 144 "costscaling.w"

/*8:*/
#line 155 "costscaling.w"

s= g->vertices+g->n;
t= g->vertices+g->n+1;

for(i= g->vertices;i<g->vertices+g->n;i++){
if(i->demanda<0){
gb_new_arc(s,i,0);
temp= malloc(sizeof(struct str_arc));
if(temp==NULL){
fprintf(stderr,"ERRO: Problemas com alocação de memória.\n");
exit(-1);
}
(s->arcs)->est= (int)temp;
(s->arcs)->cap= -(i->demanda);
}
if(i->demanda> 0){
gb_new_arc(i,t,0);
temp= malloc(sizeof(struct str_arc));
if(temp==NULL){
fprintf(stderr,"ERRO: Problemas com alocação de memória.\n");
exit(-1);
}
(i->arcs)->est= (int)temp;
(i->arcs)->cap= i->demanda;
}
}
g->n+= 2;



/*:8*/
#line 145 "costscaling.w"

/*9:*/
#line 194 "costscaling.w"



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


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,0);

temp= malloc(sizeof(struct str_arc));
if(temp==NULL){
fprintf(stderr,"ERRO: Problemas com alocação de memória.\n");
exit(-1);
}
(j->arcs)->est= (int)temp;

irmao(a)= j->arcs;
irmao(j->arcs)= a;
flx(j->arcs)= -1;
(j->arcs)->custo= -((irmao(j->arcs))->custo);
}
}
}


do{

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

s->res= -1;
inicializa_fila(g);
insere_fila(s);
while(!fila_vazia()){
i= remove_fila();

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){
j->apred= a;
if(cap_residual<i->res||i->res==-1)
j->res= cap_residual;
else
j->res= i->res;
insere_fila(j);
}
}
}
}

if(t->apred!=NULL){

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


/*:9*/
#line 146 "costscaling.w"

/*10:*/
#line 274 "costscaling.w"

viavel= TRUE;
for(a= s->arcs;a;a= a->next){
if(flx(a)!=a->cap){
viavel= FALSE;
break;
}
}
if(viavel){
for(i= g->vertices;i<g->vertices+g->n-2;i++){
if(i->demanda> 0){
for(a= i->arcs;a;a= a->next){
if(a->tip==t&&flx(a)!=a->cap){
viavel= FALSE;
}
}
}
}
}



/*:10*/
#line 147 "costscaling.w"

/*11:*/
#line 301 "costscaling.w"

g->n-= 2;
if(viavel){
for(i= g->vertices;i<g->vertices+g->n;i++){
if(i->demanda!=0){
aux= NULL;
for(a= i->arcs;a;a= a->next){
if(a->tip==s||a->tip==t){
if(aux==NULL)
i->arcs= a->next;
else
aux->next= a->next;
}
else{
aux= a;
}
}
}
}
}



/*:11*/
#line 148 "costscaling.w"



/*:7*/
#line 93 "costscaling.w"

/*14:*/
#line 364 "costscaling.w"

max_custo= -1;
for(i= g->vertices;i<g->vertices+g->n;i++){
potencial(i)= 0;
for(a= i->arcs;a;a= a->next){
c= a->custo;
if(c<0)c*= -1;
if(c> max_custo)max_custo= c;
a->custo*= g->n;
}
}
epsilon= pow(2,ceil(log(g->n*max_custo)/log(2)));


/*:14*/
#line 94 "costscaling.w"
;

iteracoes= 0;
if(viavel){
while(epsilon>=1){
/*15:*/
#line 387 "costscaling.w"

/*16:*/
#line 410 "costscaling.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
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(arco_original(a)){
custo_reduzido= a->custo-potencial(i)+potencial(a->tip);
if(custo_reduzido> 0)flx(a)= 0;
else if(custo_reduzido<0)flx(a)= a->cap;
i->exc-= flx(a);
(a->tip)->exc+= flx(a);
}
}
}


/*:16*/
#line 388 "costscaling.w"

/*17:*/
#line 434 "costscaling.w"

inicializa_fila(g);
for(i= g->vertices;i<g->vertices+g->n;i++){
if(i->exc> i->demanda)insere_fila(i);
}


/*:17*/
#line 389 "costscaling.w"

while(!fila_vazia()){
i= primeiro_fila();
/*18:*/
#line 449 "costscaling.w"

for(a= i->atual;a;a= a->next){
if(get_cap_residual(a)> 0){
custo_reduzido= a->custo-potencial(i)+potencial(a->tip);
if((custo_reduzido<0)&&(custo_reduzido>=-(epsilon/2)))
break;
}
}
if(a==NULL){
/*20:*/
#line 502 "costscaling.w"

potencial(i)+= (epsilon/2);
remove_fila();
insere_fila(i);


/*:20*/
#line 458 "costscaling.w"

i->atual= i->arcs;
}
else{
/*19:*/
#line 473 "costscaling.w"

j= a->tip;
alpha= get_cap_residual(a);
if((i->exc-i->demanda)<alpha){
alpha= (i->exc-i->demanda);
}

if(!arco_original(a)){
flx(irmao(a))-= alpha;
}
else{
flx(a)+= alpha;
}

i->exc-= alpha;
j->exc+= alpha;

if(i->exc==i->demanda){
remove_fila();
}

if((j->exc> j->demanda)&&((j->exc-alpha)<=j->demanda)){
insere_fila(j);
}


/*:19*/
#line 462 "costscaling.w"

i->atual= a;
}


/*:18*/
#line 392 "costscaling.w"

iteracoes++;
}


/*:15*/
#line 99 "costscaling.w"

epsilon= epsilon/2;
}
}
else{
fprintf(stdout,"ERRO: Instância não é viável!\n");
exit(-1);
}

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


/*:5*/
#line 725 "costscaling.w"

/*23:*/
#line 598 "costscaling.w"

int main(int argc,char*argv[]){
Graph*g;
/*29:*/
#line 710 "costscaling.w"

Arc*a;
Vertex*i;
FILE*saida;
long min,custo_reduzido;

/*:29*/
#line 601 "costscaling.w"

/*24:*/
#line 619 "costscaling.w"

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

/*:25*/
#line 624 "costscaling.w"

/*26:*/
#line 646 "costscaling.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(-4);
}
}
}

/*:26*/
#line 625 "costscaling.w"


/*:24*/
#line 602 "costscaling.w"

costscaling(g);
/*27:*/
#line 662 "costscaling.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
i->exc= 0;
}
for(min= 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));
min+= flx(a)*(a->custo/g->n);
i->exc-= flx(a);
(a->tip)->exc+= flx(a);
}
}
}
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);
if(i->demanda!=i->exc){
fprintf(stderr,"ERRO: Fluxo nao-viavel.\n");
}
}
fprintf(saida,"Custo: %ld\n",min);
fprintf(stdout,"Custo do fluxo encontrado: %ld\n",min);


/*:27*/
#line 604 "costscaling.w"

/*28:*/
#line 691 "costscaling.w"

fprintf(saida,"Custos reduzidos:\n");
for(i= g->vertices;i<g->vertices+g->n;i++){
for(a= i->arcs;a;a= a->next){
if(get_cap_residual(a)> 0){
custo_reduzido= (a->custo-potencial(inicio(a))+potencial(a->tip))/g->n;
fprintf(saida,"Custo reduzido de \"%s\" a \"%s\": %ld\n",
i->name,a->tip->name,custo_reduzido);
if(custo_reduzido<0){
fprintf(stderr,"ERRO: Fluxo nao é ótimo.\n");
}
}
}
}
fclose(saida);


/*:28*/
#line 605 "costscaling.w"

return(0);
}

/*:23*/
#line 726 "costscaling.w"



/*:30*/