# Cod sursa(job #3980)

Utilizator Data 29 decembrie 2006 21:41:13 Traseu 100 cpp done Arhiva de probleme 3.23 kb
``````//100

#include <stdio.h>
#include <string.h>
#define MIN(a,b) ((a<b)?(a):(b))
#define CAP 32000
#define INF 1000000001
#define NMAX 64

int cost[NMAX][NMAX],a[NMAX][NMAX],c[NMAX][NMAX],f[NMAX][NMAX];
int mold[NMAX][NMAX],mnew[NMAX][NMAX];
int d[NMAX],p[NMAX];
int grin[NMAX],grout[NMAX];
int i,j,n,m,C;
int x,y,z;

void leg_sursa(int ind, int source, int cp, int cst)
{
a[source][++a[source][0]] = ind;
a[ind][++a[ind][0]] = source;
c[source][ind] = cp;
cost[source][ind] = cst;

}

void leg_nod(int n1, int n2, int cp, int cst)
{
a[n1][++a[n1][0]] = n2;
a[n2][++a[n2][0]] = n1;
cost[n1][n2] = cst;
cost[n2][n1] = -cst;
c[n1][n2] = cp;
}

int belford()
{

int ok,i,j,k;

for (i = 0; i <= n+1; i++) { d[i] = INF; p[i] = -1; }

p[0] = -1;
d[0] = 0;
ok = 1;

for (k = 1; k <= n+1 && ok; k++)
for (i = 0 , ok = 0; i <= n+1; i++)
for (j = 1; j <= a[i][0]; j++)
{
int t = a[i][j];

if (c[i][t] > f[i][t]  && d[t] > d[i] + cost[i][t])
{
d[t] = d[i] + cost[i][t];
p[t] = i;
ok = 1;
}
}

return d[n+1] < INF;
}

void royf()
{

int k, i, j;

memcpy(mnew, cost, sizeof(cost));
memcpy(mold, cost, sizeof(cost));

for (k = 1; k <= n; k++)
{
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (mold[i][k] < INF && mold[k][j] < INF)
mnew[i][j] = MIN(mnew[i][j], mold[i][k] + mold[k][j]);

memcpy(mold, mnew, sizeof(mnew));
}

//memcpy(cost, mnew, sizeof(mnew));

}

void init()
{
int i, j;

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) cost[i][j] = INF * (i != j);
}

int main()
{

freopen("traseu.in","r",stdin);
freopen("traseu.out","w",stdout);

scanf("%d %d",&n,&m);

init();

for (i = 1; i <= m; i++)
{
scanf("%d %d %d",&x,&y,&z);

cost[x][y] = z;
grin[y]++; grout[x]++;
C += z;
}

royf();

for (i = 1; i <= n; i++)
{
if (grin[i] > grout[i]) leg_sursa(i, 0, grin[i]-grout[i], 0);
if (grin[i] < grout[i]) leg_sursa(n+1, i, grout[i]-grin[i], 0);
}

for (i = 1; i <= n; i++)
for (j = 1;j <= n; j++)
if ( grin[i] > grout[i] && grin[j] < grout[j] )
leg_nod(i, j, CAP, mnew[i][j]);

while ( 1 )
{

int minim = INF;

if ( belford() )
{

for (i = n+1; p[i] >= 0; i = p[i])
{
int cap = c[p[i]][i] - f[p[i]][i];

minim = MIN(minim, cap);
}

for (i = n+1; p[i] >= 0; i = p[i])
{
f[p[i]][i] += minim;
f[i][p[i]] -= minim;
}

C += minim * d[n+1];
}
else break;
}

printf("%d\n",C);

fclose(stdin);
fclose(stdout);

return 0;
}
``````