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

#define demanda u.I
#define exc v.I
#define res v.I
#define apred w.A
#define dist x.I
#define nafila y.I
#define vertice z.V \

#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 \

/*29:*/
#line 750 "cyclecanceling.w"

/*30:*/
#line 763 "cyclecanceling.w"

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


/*:30*/
#line 751 "cyclecanceling.w"

/*32:*/
#line 797 "cyclecanceling.w"

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

/*:32*/
#line 752 "cyclecanceling.w"

/*21:*/
#line 543 "cyclecanceling.w"

Vertex*ini,*fim,*zero;
Vertex*max;


void enqueue(Vertex*i){
fim->vertice= i;
i->nafila= TRUE;
fim++;
if(fim> max){
fim= zero;
}
if(fim==ini){
fprintf(stderr,"ERRO: Fila excedeu sua capacidade.\n");
exit(-1);
}
}

void init_queue(Graph*g,Vertex*i){
Vertex*j;
ini= g->vertices;
fim= g->vertices;
zero= g->vertices;
max= g->vertices+g->n;

for(j= g->vertices;j<g->vertices+g->n;j++){
j->nafila= FALSE;
}
enqueue(i);

return;
}

boolean empty_queue(){
if(ini==fim)
return TRUE;
return FALSE;
}

Vertex*remove_first(){
Vertex*i;
if(!empty_queue()){
i= ini->vertice;
ini++;
if(ini> max){
ini= zero;
}
i->nafila= FALSE;
return i;
}
return NULL;
}


Vertex*last_enqueued(){
if(!empty_queue()){
return fim->vertice;
}
return NULL;
}


boolean is_enqueued(Vertex*i){
return i->nafila;
}



/*:21*/
#line 753 "cyclecanceling.w"

/*12:*/
#line 322 "cyclecanceling.w"

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


/*:12*/
#line 754 "cyclecanceling.w"

/*13:*/
#line 333 "cyclecanceling.w"

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


/*:13*/
#line 755 "cyclecanceling.w"

/*5:*/
#line 85 "cyclecanceling.w"

void cyclecanceling(Graph*g){
/*20:*/
#line 517 "cyclecanceling.w"

int iteracoes,d,passo;
long cap_residual,capres_ciclo;
boolean viavel;
Vertex*i,*j,*s,*t,*origem,*ultimo,*i_ciclo;
Arc*a,*aux;
void*temp;




/*:20*/
#line 87 "cyclecanceling.w"

/*6:*/
#line 117 "cyclecanceling.w"

for(i= g->vertices;i<g->vertices+g->n;i++){
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 88 "cyclecanceling.w"

/*7:*/
#line 140 "cyclecanceling.w"

/*8:*/
#line 151 "cyclecanceling.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 141 "cyclecanceling.w"

/*9:*/
#line 190 "cyclecanceling.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;
init_queue(g,s);
while(!empty_queue()){
i= remove_first();

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;
enqueue(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 142 "cyclecanceling.w"

/*10:*/
#line 269 "cyclecanceling.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 143 "cyclecanceling.w"

/*11:*/
#line 296 "cyclecanceling.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 144 "cyclecanceling.w"



/*:7*/
#line 89 "cyclecanceling.w"


iteracoes= 0;
if(viavel){
do{
/*14:*/
#line 358 "cyclecanceling.w"

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

origem= g->vertices;
do{
/*15:*/
#line 398 "cyclecanceling.w"

passo= 0;
ultimo= origem;
origem->dist= 0;
origem->apred= (Arc*)origem;

init_queue(g,origem);
while((passo!=g->n)&&(!empty_queue())){
i= remove_first();

for(a= i->arcs;a;a= a->next){
if(get_cap_residual(a)> 0){
d= i->dist+a->custo;
j= a->tip;

if(d<j->dist||(j->apred==NULL&&j!=origem)){
j->dist= d;
j->apred= a;
if(!is_enqueued(j)){
enqueue(j);
}
}
}
}

if(i==ultimo){
ultimo= last_enqueued();
passo++;
}
}


i_ciclo= NULL;
if(!empty_queue()){

for(i= g->vertices;i<g->vertices+g->n;i++)
i->dist= 0;

ultimo->dist= 1;
i= inicio(ultimo->apred);
while(i->dist!=1){
i->dist= 1;
i= inicio(i->apred);
}
i_ciclo= i;
}


/*:15*/
#line 366 "cyclecanceling.w"

if(i_ciclo==NULL){
/*16:*/
#line 456 "cyclecanceling.w"

origem= NULL;
for(j= g->vertices;j<g->vertices+g->n;j++){
if(j->apred==NULL){
origem= j;
break;
}
}


/*:16*/
#line 368 "cyclecanceling.w"

}
}
while(i_ciclo==NULL&&origem!=NULL);


/*:14*/
#line 94 "cyclecanceling.w"

if(i_ciclo!=NULL){
/*17:*/
#line 472 "cyclecanceling.w"

/*18:*/
#line 480 "cyclecanceling.w"

init_queue(g,i_ciclo);
capres_ciclo= get_cap_residual(i_ciclo->apred);

for(i= inicio(i_ciclo->apred);i!=i_ciclo;i= inicio(i->apred)){
a= i->apred;
if(get_cap_residual(a)<capres_ciclo){
capres_ciclo= get_cap_residual(a);
}
enqueue(i);
}



/*:18*/
#line 473 "cyclecanceling.w"

/*19:*/
#line 501 "cyclecanceling.w"

while(!empty_queue()){
i= remove_first();
a= i->apred;

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


/*:19*/
#line 474 "cyclecanceling.w"


/*:17*/
#line 96 "cyclecanceling.w"

iteracoes++;
}
}
while(i_ciclo!=NULL);
}
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 756 "cyclecanceling.w"

/*22:*/
#line 619 "cyclecanceling.w"

int main(int argc,char*argv[]){
Graph*g;
/*28:*/
#line 741 "cyclecanceling.w"

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

/*:28*/
#line 622 "cyclecanceling.w"

/*23:*/
#line 640 "cyclecanceling.w"

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

/*:24*/
#line 645 "cyclecanceling.w"

/*25:*/
#line 667 "cyclecanceling.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);
}
}
}

/*:25*/
#line 646 "cyclecanceling.w"


/*:23*/
#line 623 "cyclecanceling.w"

cyclecanceling(g);
/*26:*/
#line 683 "cyclecanceling.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;
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);


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

/*27:*/
#line 722 "cyclecanceling.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-((a->tip)->dist-(inicio(a))->dist);
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);


/*:27*/
#line 626 "cyclecanceling.w"

return(0);
}

/*:22*/
#line 757 "cyclecanceling.w"



/*:29*/