# Cod sursa(job #85239)

Utilizator Data 20 septembrie 2007 17:36:35 Traseu 100 cpp done Arhiva de probleme 2.02 kb
#include<stdio.h>
#define Nm 62
#define Inf 1000000000
#define min(a,b) ((a)<(b)?(a):(b))
int G[Nm][Nm],K[Nm][Nm],C[Nm][Nm],F[Nm][Nm],De[Nm],Di[Nm],D[Nm],n;
int X[Nm*Nm],Y[Nm*Nm],Q[Nm*Nm],Dm[Nm],Min[Nm],Pre[Nm],m,ans;

{
int i,j;

freopen("traseu.in","r",stdin);
scanf("%d%d",&n,&m);

for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
K[i][j]=Inf;

for(i=0;i<m;++i)
{
scanf("%d%d%d",X+i,Y+i,&j);
++De[X[i]]; ++Di[Y[i]];
K[X[i]][Y[i]]=j; ans+=j;
}
}

int Bellman_Ford()
{
int l,r,x,y,i;

Q[l=r=0]=0; Min[0]=Inf; Dm[0]=0;
for(i=1;i<=n+1;++i)
Dm[i]=Inf;

while(l<=r)
{
x=Q[l++];
for(i=0;i<D[x];++i)
{
y=G[x][i];
if(F[x][y]<C[x][y] && Dm[x]+K[x][y]<Dm[y])
{
Dm[y]=Dm[x]+K[x][y];
Min[y]=min(Min[x],C[x][y]-F[x][y]);
Pre[y]=x;
Q[++r]=y;
}
}
}

return Dm[n+1]!=Inf;
}

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

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

for(i=1;i<=n;++i)
if(Di[i]>De[i])
for(j=1;j<=n;++j)
if(De[j]>Di[j])
G[i][D[i]++]=j, G[j][D[j]++]=i,
C[i][j]=Inf, K[j][i]=-K[i][j];

for(i=1;i<=n;++i)
{
if(Di[i]>De[i])
G[0][D[0]++]=i, C[0][i]=Di[i]-De[i];
if(De[i]>Di[i])
G[i][D[i]++]=n+1, C[i][n+1]=De[i]-Di[i];
}

while(Bellman_Ford())
{
ans+=Min[n+1]*Dm[n+1];
i=n+1;
while(i)
{
F[Pre[i]][i]+=Min[n+1];
F[i][Pre[i]]-=Min[n+1];
i=Pre[i];
}
}
}

void write()
{
freopen("traseu.out","w",stdout);
printf("%d\n",ans);
}

int main()
{