# Cod sursa(job #20389)

Utilizator Data 21 februarie 2007 13:34:19 Traseu 100 cpp done Arhiva de probleme 2.36 kb
``````# include <stdio.h>

# define  _fin  "traseu.in"
# define  _fout "traseu.out"

# define  maxn  70
# define  maxm  3000

# define  inf   1000000027

int m, n, v[maxn][maxn], vc[maxn][maxn];	// cost

int cap[maxn][maxn], f[maxn][maxn];
int d[maxn], prec[maxn], cost;
int s, t, sol;

{
freopen(_fin, "r", stdin);
int i, x, y, c, j;

for (i=1; i<maxn; i++) for (j=1; j<maxn; j++) vc[i][j] = inf;
for (i=1; i<maxn; i++) vc[i][i] = 0;

for (scanf("%d%d", &n, &m), i=1; i<=m; i++)
scanf("%d %d %d", &x, &y, &c), sol += c,
vc[x][y] = c, v[x][y] = 1, dg[x]++, dg[y]--;
}

inline int min(int a, int b) { return a<b?a:b; }

void presolve()
{
int i, j, k;

for (k=1; k<=n; k++)
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
vc[i][j] = min( vc[i][j], vc[i][k] + vc[k][j] );

// create flow network
s=n+1, t=n+2;

for (i=1; i<=n; i++)
if ( dg[i] < 0 )				// grad iesire < grad intrare
v[s][i]=2, vc[s][i]=0,
cap[s][i]=-dg[i],
v[i][s]=2, vc[i][s]=0,		// NEW
cap[i][s]=0;				// NEW
else if ( dg[i] > 0 )
v[i][t]=2, vc[i][t]=0,
cap[i][t]=dg[i],
v[t][i]=2, vc[t][i]=0,		// NEW
cap[t][i]=0;				// NEW

for (i=1; i<=n; i++)
if ( v[s][i] )
for (j=1; j<=n; j++)
if ( v[j][t] )
v[i][j] = 2, cap[i][j] = inf,
v[j][i] = 2, cap[j][i] = 0, vc[j][i] = -vc[i][j];
}

int bellmanFord()
{
int i, j, step, relax=1, w;

for (i=1; i<maxn; i++) d[i] = inf, prec[i]=-1;
d[s] = prec[s] = 0;

for (step=1; step<n+2 && relax; step++)
{
relax = 0;

for (i=1; i<=n+2; i++)
for (j=1; j<=n+2; j++)
if ( v[i][j]==2 && cap[i][j]-f[i][j] > 0 )
if ( d[j] > d[i] + vc[i][j] )
d[j] = d[i] + vc[i][j],
prec[j] = i, relax=1;
}

if ( prec[t] == -1 ) return 0;	// done

for (w=t; prec[w]; w=prec[w])
++f[ prec[w] ][ w ],
--f[ w ][ prec[w] ];

cost = d[t];

return 1;
}

void solve()
{
presolve();

while ( bellmanFord() )
sol += cost;
/*    int i, j;

for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if ( v[i][j]==2 )
sol += vc[i][j] * f[i][j];  */
}

void writef()
{
freopen(_fout, "w", stdout);
printf("%d\n", sol);
}

int main()
{