# Cod sursa(job #13575)

Utilizator Data 7 februarie 2007 01:30:06 Traseu 100 cpp done Arhiva de probleme 2.27 kb
``````#include <stdio.h>
#include <string>

#define maxn 70
#define maxx 3710
#define inf 10000
#define maxv 1000000000

int g[maxn],in[maxn],out[maxn];
int x[maxx],y[maxx],z[maxx],a[maxx];
int f[maxn][maxn],cap[maxn][maxn],cost[maxn][maxn];
int n,m,sol;
int found,from[maxn],c[maxn];

int BellmanFord(int S,int D)
{
int i,j,stop=0,min=maxv;

for (i=0;i<=n+1;i++) c[i]=maxv;
c[S]=0;

while (!stop)
{
stop=1;

for (i=0;i<=n+1;i++)
for (j=g[i];j<g[i+1];j++)
if ((cap[i][a[j]]-f[i][a[j]]>0) && (c[i]+cost[i][a[j]]<c[a[j]]))
{
from[a[j]]=i;
c[a[j]]=c[i]+cost[i][a[j]];
stop=0;
}
}

if (c[D]!=maxv)
{
found=1;

i=D;
while (i!=S)
{
if (cap[from[i]][i]-f[from[i]][i]<min) min=cap[from[i]][i]-f[from[i]][i];
i=from[i];
}

i=D;
while (i!=S)
{
f[from[i]][i]+=min;
f[i][from[i]]-=min;
i=from[i];
}

return c[D]*min;
}

return 0;
}

int Flux()
{
int rez=0;
found=1;

while (found)
{
found=0;
rez+=BellmanFord(0,n+1);
}

return rez;
}

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

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

int i,j,aux;

for (i=1;i<=m;i++)
{
scanf("%d %d %d",&x[i],&y[i],&z[i]);
g[x[i]]++;
g[y[i]]++;
in[x[i]]++;
out[y[i]]++;
cap[x[i]][y[i]]=inf;
cost[x[i]][y[i]]=z[i];
cost[y[i]][x[i]]=-z[i];
sol+=z[i];
}

for (i=1;i<=n;i++)
if (out[i]>in[i])
{
g[0]++;
g[i]++;
cap[0][i]=out[i]-in[i];
m++;
x[m]=0;
y[m]=i;
}

for (i=1;i<=n;i++)
if (out[i]<in[i])
{
g[i]++;
g[n+1]++;
cap[i][n+1]=in[i]-out[i];
m++;
x[m]=i;
y[m]=n+1;
}

for (i=1;i<=n+2;i++) g[i]+=g[i-1];

for (i=1;i<=m;i++)
{
a[g[x[i]]--]=y[i];
a[g[y[i]]--]=x[i];
}

for (i=0;i<=n+2;i++) g[i]++;

sol+=Flux();

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

return 0;
}
``````