Pagini recente » Cod sursa (job #1427167) | Cod sursa (job #1606470) | Cod sursa (job #969224) | Cod sursa (job #510352) | Cod sursa (job #441191)
Cod sursa(job #441191)
# 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;
}