Cod sursa(job #441191)

Utilizator MciprianMMciprianM MciprianM Data 12 aprilie 2010 20:07:07
Problema Flux maxim de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 kb
# include <fstream>
# include <vector>

using namespace std;

const int MAXN = 1024, inf = 2000000001;
int maxFlow, minCost;
int N, M, S, D;
int cap [ MAXN ] [ MAXN ], cost [ MAXN ] [ MAXN ];
int dist [ MAXN ], from [ MAXN ];
vector <int> G [ MAXN ];

void oneSourceMultipleDestinationsMinPaths (){

	int i, j;
	vector <int> :: iterator it;
	
	for ( i = 1; i <= N; ++ i )
		dist [ i ] = inf;
	dist [ S ] = 0;
	memset ( from, -1, sizeof ( from ) );
	
	for ( i = 1; i < N; ++ i )
		for ( j = 1; j <= N; ++ j )
			for ( it = G [ j ] . begin (); it != G [ j ] . end (); ++ it )
				
				if ( cap [ j ] [ * it ] > 0 && dist [ j ] != inf &&
						dist [ * it ] > dist [ j ] + cost [ j ] [ * it ] ){
							
							dist [ * it ] = dist [ j ] + cost [ j ] [ * it ];
							from [ * it ] = j;
							
				}
	
}

void findAugmentingPathOfMinCost ( int &flow, int &cst ){
	
	int dad;
	
	flow = inf; cst = 0;
	
	oneSourceMultipleDestinationsMinPaths ();
	
	if ( from [ D ] == -1 ){
		flow = 0;
		return;
	}
	
	dad = D;
	while ( from [ dad ] != -1 ){
		
		cst += cost [ from [ dad ] ] [ dad ];
		if ( cap [ from [ dad ] ] [ dad ] < flow )
			flow = cap [ from [ dad ] ] [ dad ];
		dad = from [ dad ];
		
	}
	
	dad = D;
	while ( from [ dad ] != -1 ){
		
		cap [ dad ] [ from [ dad ] ] += flow;
		cap [ from [ dad ] ] [ dad ] -= flow;
		dad = from [ dad ];
		
	}
	
}

void fmcm (){
	
	int flux, cst;
	
	do{
	
		findAugmentingPathOfMinCost ( flux, cst );
		maxFlow += flux;
		minCost += flux * cst;
		
	}	while ( flux > 0 );
	
}

void creareGraf (){
	
	/* Graful contine cel mult un arc intre oricare doua noduri x si y,
		iar daca ( x, y ) apartine lui E, atunci ( y, x ) nu apartine lui E,
		unde E este multimea arcelor	*/
	
	int i, x, y;
	ifstream f ( "fmcm.in" );
	
	f >> N >> M >> S >> D;
	for ( i = 0; i < M; ++ i ){
		f >> x >> y;
		f >> cap [ x ] [ y ] >> cost [ x ] [ y ];
		cost [ y ] [ x ] = - cost [ x ] [ y ];
		G [ x ] . push_back ( y );
		G [ y ] . push_back ( x );
	}
	
	f . close ();
	
}

void afis (){
	
	ofstream g ( "fmcm.out" );
	g << maxFlow << ' ' << minCost << '\n';
	g . close ();
	
}

int main(){
	
	creareGraf ();
	fmcm ();
	afis ();
	
	return 0;
	
}