# Cod sursa(job #928641)

Utilizator Data 26 martie 2013 16:34:30 Traseu 100 cpp done Arhiva de probleme 2.7 kb
``````#include <cstdio>

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define pb push_back
#define FORIT( it,v ) for( typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it )

const int INF=0x3f3f3f3f, max_n=66, Sink=65, Source=0, empty=-1;

int n,m;
int a,b,c;
int i,j,k;

int Nr[max_n];
vector<int> Vertex[max_n];
int Cost[max_n][max_n];
int C[max_n][max_n], F[max_n][max_n], Best[max_n], Father[max_n]; // flux
bool Inside[max_n];
queue<int> Qu;

int maxFlow, flowCost;

void get_min( int &a, int b ){
if( a>b )
a=b;
}

bool bfs(){
int nod;
Inside[Source]=true;
Qu.push(Source);
Best[Source]=0;
Father[Source]=Source;
while( !Qu.empty() ){
nod=Qu.front();
Inside[nod]=false;
Qu.pop();
FORIT( it, Vertex[nod] ){
if( Best[*it] > Best[nod]+Cost[nod][*it] && ( C[nod][*it] > F[nod][*it]  ) ){
Best[*it] = Best[nod]+Cost[nod][*it];
Father[*it] = nod;
if( !Inside[*it] ){
Inside[*it]=true;
Qu.push(*it);
}
}
}
}
if( Father[Sink] == empty )
return 0;
int mn=INF;
for( nod=Sink; nod!=Source; nod=Father[nod] ) get_min( mn, C[Father[nod]][nod] - F[Father[nod]][nod] );
for( nod=Sink; nod!=Source; nod=Father[nod] ){
F[Father[nod]][nod]+=mn;
F[nod][Father[nod]]-=mn;
}
flowCost+=mn*Best[Sink];
maxFlow+=mn;
return 1;
}

int main(){

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

scanf("%d %d", &n, &m);
for( i=1; i<=n; Cost[i][i]=0,++i )
for( j=1; j<=n; ++j )
Cost[i][j]=INF;

for( i=1; i<=m; ++i ){
scanf("%d %d %d", &a, &b, &c );
Cost[a][b]=c;
flowCost+=c;
Nr[a]--;
Nr[b]++;
}
for( k=1; k<=n; ++k )
for( i=1; i<=n; ++i )
for( j=1; j<=n; ++j )
get_min( Cost[i][j], Cost[i][k]+Cost[k][j] );
for( i=1; i<=n; ++i ){
if( Nr[i]>0 ){
// ajung mai multe
Vertex[Source].push_back(i);
Vertex[i].push_back(Source);
C[Source][i]=Nr[i];
}
if( Nr[i]<0 ){
// pleaca mai multe ..
Vertex[i].push_back(Sink);
Vertex[Sink].push_back(i);
C[i][Sink]=-Nr[i];
}
}

for( i=1; i<=n; ++i )
if( Nr[i]>0 )
for( j=1; j<=n; ++j )
if( Nr[j]<0 ){
Cost[j][i]=-Cost[i][j];
Vertex[i].push_back(j);
Vertex[j].push_back(i);
C[i][j]=INF;
}
/*	for( i=1; i<=n; ++i,cerr<<"\n" )
for( j=1; j<=n; ++j )
cerr<<Cost[i][j]<<"\t";*/

/*	for( i=1; i<=n; ++i )
cerr<<Nr[i]<<"\t";
cerr<<"\n\n";*/
for( i=0; i<=Sink; ++i ){
Father[i]=empty;
Best[i]=INF;
Inside[i]=false;
}
while( bfs() ){
for( i=0; i<=Sink; ++i ){
Father[i]=empty;
Best[i]=INF;
Inside[i]=false;
}
}
//   cerr<<maxFlow<<"\n";
printf("%d\n",flowCost);
return 0;
}
``````