Pagini recente » Profil UPB_Ciurel_Grigore_Tiu | Diferente pentru planificare/sedinta-20091023 intre reviziile 54 si 27 | Tembelizor | Tnia | Cod sursa (job #1707030)
#include <cstdio>
#include <vector>
#include <deque>
#include <bitset>
#include <cstring>
#include <algorithm>
const int SIZE = 4e3 + 5;
const int INFI = 0x3f3f3f3f;
int node2, edge_capacity, edge_cost;
int minim, max_flow, min_cost, start_node, finish_node, cnt_nodes, cnt_edges, node1;
int capacity[SIZE][SIZE], cost[SIZE][SIZE], flow[SIZE][SIZE], dp[SIZE], father[SIZE];;
std::vector <int> edge[SIZE]; std::deque <int> my_queue; std::bitset <SIZE> marked;
inline bool bf( int start_node, int finish_node ) {
marked.reset(); marked[start_node] = 1;
my_queue.clear(); my_queue.push_back(start_node);
memset( dp, INFI, sizeof(dp) ); dp[start_node] = 0;
bool ok = false;
while( !my_queue.empty() ) {
int node = my_queue.front();
std::vector <int> :: iterator it;
for( it = edge[node].begin(); it != edge[node].end(); it ++ ) {
int next_node = *it;
if( flow[node][next_node] == capacity[node][next_node] )
continue;
if( dp[next_node] > dp[node] + cost[node][next_node] ) {
dp[next_node] = dp[node] + cost[node][next_node];
father[next_node] = node;
if( !marked[next_node] ) {
marked[next_node] = 1;
my_queue.push_back(next_node);
if( next_node == finish_node )
ok = true;
}
}
}
marked[node] = 0;
my_queue.pop_front();
}
return ok;
}
int main( int argc, const char *argv[] ) {
freopen( "fmcm.in" , "r", stdin );
freopen( "fmcm.out", "w", stdout );
scanf( "%d %d %d %d", &cnt_nodes, &cnt_edges, &start_node, &finish_node );
for( int i = 1; i <= cnt_edges; i ++ ) {
scanf( "%d %d %d %d", &node1, &node2, &edge_capacity, &edge_cost );
capacity[node1][node2] = edge_capacity; cost[node1][node2] = edge_cost;
capacity[node2][node1] = 0 ; cost[node2][node1] = -edge_cost;
edge[node1].push_back(node2);
}
while( bf( start_node, finish_node ) ) {
minim = INFI;
for( int node = finish_node; node != start_node; node = father[node] )
minim = std::min( minim, capacity[ father[node] ][node] - flow[ father[node] ][node] );
max_flow += minim;
for( int node = finish_node; node != start_node; node = father[node] ) {
min_cost += minim * cost[ father[node] ][node];
flow[ father[node] ][node] += minim;
flow[node][ father[node] ] -= minim;
}
}
printf( "%d\n", max_flow, min_cost );
return 0;
}