Cod sursa(job #1707030)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 24 mai 2016 00:57:06
Problema Flux maxim de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.75 kb
#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;
}