# Cod sursa(job #429919)

Utilizator Data 30 martie 2010 16:54:47 Traseu 100 cpp done Arhiva de probleme 2.13 kb
``````#include <cstdio>
#include <vector>
using namespace std;
#define pb push_back
#define mp make_pair
#define NMAX 64
#define oo 1000000
vector <int> M[NMAX];
int C[NMAX][NMAX], cap[NMAX][NMAX];
int Sum,n,gi[NMAX],go[NMAX],dist[NMAX],s,d,from[NMAX],Q[300];
bool viz[NMAX],gasit;

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

int i,j;
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
C[i][j]=oo;

for (i=0;i<m;++i)
{ int x,y,ct;
scanf("%d %d %d",&x,&y,&ct);
C[x][y]=ct;
gi[y]++; go[x]++;
Sum+=ct;
}
}

int Flux()
{
int x,st,dr; unsigned i;
for (i=0;i<M[s].size();++i) { dist[M[s][i]]=oo; from[M[s][i]]=-1; }
for (i=0;i<M[d].size();++i) { dist[M[d][i]]=oo; from[M[d][i]]=-1; }
memset(viz,0,sizeof(viz));
dist[d]=oo; from[d]=-1;
dist[s]=0; viz[s]=1; st=dr=0; Q[0]=s;
while (st<=dr)
{
x=Q[st++];
for (i=0;i<M[x].size();++i)
if (cap[x][M[x][i]]>0 && dist[M[x][i]]>dist[x]+C[x][M[x][i]])
{
dist[M[x][i]]=dist[x]+C[x][M[x][i]] ;
from[M[x][i]]=x;
if (!viz[M[x][i]])
{
viz[M[x][i]]=1;
Q[++dr]=M[x][i];
}
}
viz[x]=0;
}

if (from[d]==-1) return 0;
gasit=1;
int flux=oo;
for (i=d; i!=s; i=from[i]) flux=min(flux,cap[from[i]][i]);
for (i=d; i!=s; i=from[i])
cap[from[i]][i]-=flux, cap[i][from[i]]+=flux;
return flux*dist[d];
}

int main()
{
Sum=0;
citire();

//drumuri minime
int x,y,z;
unsigned i,j;
for (y=1;y<=n;++y)
for (x=1;x<=n;++x)
for (z=1;z<=n;++z)
if (C[x][z]>C[x][y]+C[y][z])
C[x][z]=C[x][y]+C[y][z];

s=0;d=n+1;
memset(cap,0,sizeof(cap));
for (i=1;i<=n;++i)
{
if (gi[i]>go[i]) {M[s].pb(i); M[i].pb(s); C[s][i]=C[i][s]=0; cap[s][i]=gi[i]-go[i];} else
if (gi[i]<go[i]) {M[d].pb(i); M[i].pb(d); C[d][i]=C[i][d]=0; cap[i][d]=go[i]-gi[i];}
}

for (i=0;i<M[s].size();++i)
{
x=M[s][i];
for (j=0;j<M[d].size();++j)
{
y=M[d][j];
cap[x][y]=oo; C[y][x]=-C[x][y];
M[x].pb(y); M[y].pb(x);
}
}

do
{
gasit=0;
Sum+=Flux();
}
while (gasit);

freopen("traseu.out","w",stdout);
printf("%d\n",Sum);
return 0;
}
``````