# Cod sursa(job #21877)

Utilizator Data 24 februarie 2007 20:39:12 Traseu 20 cpp done Arhiva de probleme 3.96 kb
``````/*
Complexitate: O(N^4)
*/

#include <stdio.h>

#define infile "traseu.in"
#define outfile "traseu.out"
#define NMAX 61
#define INF 1000000000
struct NOD {int x,c; NOD *adr;};

FILE *fin,*fout;
int n,n_ini;
int cost_minim=0;
NOD *prim[2*NMAX+2];
short int cap[2*NMAX+2][2*NMAX+2];
short int prec[2*NMAX+2];
int bfcost[2*NMAX+2];

inline void adaug_st(NOD *(&prim), int x, int c)
{
NOD *a=new NOD;
a->x=x;
a->c=c;
prim=a;
}

void citire_init()
{
int i,j,m,u,v,c;
fin=fopen(infile,"r");
fscanf(fin,"%d %d",&n,&m);
suma=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i==j)
cost[i][j]=0;
else
cost[i][j]=INF;
for(i=0;i<n;i++)
for(i=0;i<m;i++)
{
fscanf(fin,"%d %d %d",&u,&v,&c);
u--; v--;
suma+=c;
cost[u][v]=c;
}
fclose(fin);
}

void roy_floyd()
{
int i,j,k;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
if(i!=k)
for(j=0;j<n;j++)
if(j!=k && j!=i)
if(cost[i][j] > cost[i][k]+cost[k][j])
cost[i][j] = cost[i][k]+cost[k][j];
}

void constr_retea()
{
int i,j;
for(i=0;i<2*n+2;i++)
prim[i]=NULL;
for(i=1;i<=n;i++)
{
cap[i][0]=0;
}
for(i=n+1;i<=2*n;i++)
{
cap[2*n+1][i]=0;
}
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
{
cap[i][j]=1;
cap[j][i]=0;
}
n_ini=n;
n=2*n+2;
}

void greedy()
{
int i;
NOD *b;
for(i=1;i<=n_ini;i++)
{
b=prim[i];
while(b)
{
if(b->x>=n_ini+1 && b->x<=2*n_ini && cap[0][i] && cap[b->x][2*n_ini+1])
{
cap[0][i]--; cap[i][0]++;
cap[b->x][2*n_ini+1]--; cap[2*n_ini+1][b->x]++;
cap[i][b->x]--; cap[b->x][i]++;
}
}
}
}

void bellman_ford()
{
int i;
NOD *b;
for(i=1;i<n;i++)
bfcost[i]=INF;
prec[0]=-1;
bfcost[0]=0;
for(i=0;i<n;i++)
{
b=prim[i];
while(b)
{
if(cap[i][b->x] && bfcost[b->x]>bfcost[i]+b->c && bfcost[i]!=INF)
{
bfcost[b->x]=bfcost[i]+b->c;
prec[b->x]=i;
}
}
}
}

void cuplaj()
{
int u,v,min;
greedy(); // O(M)
do{
bellman_ford();
if(bfcost[n-1]!=INF)
{
u=prec[n-1];
v=n-1;
min=INF;
while(u!=-1)
{
if(min>cap[u][v])
min=cap[u][v];
v=u;
u=prec[u];
}
u=prec[n-1];
v=n-1;
while(u!=-1)
{
cap[u][v]-=min;
cap[v][u]+=min;
v=u;
u=prec[u];
}
}
}while(bfcost[n-1]!=INF);
}

int main()
{
int i,j;
citire_init();
roy_floyd();
constr_retea();
cuplaj();

n=n_ini;
cost_minim=0;
for(i=1;i<=n;i++)