Pagini recente » Cod sursa (job #1610933) | Cod sursa (job #1002330) | Cod sursa (job #1769461) | Cod sursa (job #224958) | Cod sursa (job #1444570)
/*
* e_032_max_flow_min_cost_diskstra_matrices.cpp
*
* Created on: May 29, 2015
* Author: Marius
*/
#include <iostream>
#include <utility>
using namespace std;
#include <fstream>
#include <queue>
#include <list>
#include <vector>
#include <string>
#include <algorithm>
#include <limits>
#include <set>
namespace e_032_max_flow_min_dijsktra_matrices_nms
{
struct Edge
{
int u, v; // edge u to v
int c; // the capacity
int z; // the cost of the edge
int dir; // direction: forward (1) or backward (-1) edge
Edge* re; // pointer to the reverse edge in the graph
};
void find_best_cost_bellman_ford(int S, vector<vector<Edge*>>& adj_list, vector<int>& best_cost)
{
int N = adj_list.size() - 1;
list<int> Q;
vector<char> in_queue;
vector<int> bfs_levels; // the level of the nodes in a bfs search from S
in_queue.resize(N + 1);
bfs_levels.resize(N + 1);
std::fill(best_cost.begin(), best_cost.end(), std::numeric_limits<int>::max());
std::fill(in_queue.begin(), in_queue.end(), 0);
Q.push_back(S);
in_queue[S] = 1;
best_cost[S] = 0;
bfs_levels[S] = 1;
int max_bfs_level = 1;
//while ( !Q.empty() && max_bfs_level <= N )
// the problem statement guarantees there are no negative cycles
while (!Q.empty())
{
// pop one element from the list
int u = Q.front();
Q.pop_front();
in_queue[u] = 0;
//parse the adjacency list and look for possible better costs
for (auto e : adj_list[u])
{
if (e->c <= 0) continue; //only positive capacities are processed here
int v = e->v;
int candidate_cost = best_cost[u] + e->z;
if (candidate_cost < best_cost[v])
{
best_cost[v] = candidate_cost;
bfs_levels[v] = bfs_levels[u] + 1;
max_bfs_level = max(bfs_levels[v], max_bfs_level);
if (!in_queue[v])
{
Q.push_back(v);
in_queue[v] = 1;
}
}
}
}
}
int find_max_flow_ford_fulkerson(int N, int S, int D, vector<vector<Edge*>>& adj_list)
{
int max_flow = 0;
//find the initial best cost using the bellman ford algorithm
//the algorithm only uses the cost and ignores the capacities of the edges
vector<int> best_cost_prev, best_cost_new;
best_cost_prev.resize(N + 1);
best_cost_new.resize(N + 1);
find_best_cost_bellman_ford(S, adj_list, best_cost_prev);
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, std::greater<pii>> Q;
vector<int> best_cost_augmented;
vector<char> in_queue;
vector<Edge*> parent_edges;
best_cost_augmented.resize(N + 1);
in_queue.resize(N + 1);
parent_edges.resize(N + 1);
bool has_s2t_path = true;
while (has_s2t_path)
{
//Dijkstra
std::fill(best_cost_augmented.begin(), best_cost_augmented.end(),
std::numeric_limits<int>::max() / 2);
std::fill(best_cost_new.begin(), best_cost_new.end(),
std::numeric_limits<int>::max() / 2);
best_cost_augmented[S] = 0;
best_cost_new[S] = 0;
for (int u = 1; u <= N; u++)
Q.push(make_pair(best_cost_augmented[u], u));
std::fill(in_queue.begin(), in_queue.end(), 1);
for (auto& ep : parent_edges)
ep = 0;
//find a path from source to sink in the residual graph
//only edges with positive capacities should be included in the path
while (!Q.empty())
{
//pop the first element in the set
auto& top = Q.top();
int u = top.second;
int c = top.first;
Q.pop();
//if not the true minimum, do nothing
//take care about multiple costs for the same node in the priority queue
if (c > best_cost_augmented[u]) continue;
in_queue[u] = 0; // no longer in queue
for (auto e : adj_list[u])
{
int v = e->v;
//edge with positive capacity
if (in_queue[v] == 1 && e->c > 0)
{
//check-update the cost of the node
int augmented_cost_uv = best_cost_augmented[u] + e->z + best_cost_prev[u]
- best_cost_prev[v];
if (augmented_cost_uv < best_cost_augmented[v])
{
//update the cost of the node
best_cost_augmented[v] = augmented_cost_uv;
//insert the updated cost
//take care, the previous best cost, is still in the priority queue
Q.push(make_pair(best_cost_augmented[v], v));
parent_edges[v] = e;
//update the real best cost
best_cost_new[v] = best_cost_new[u] + e->z;
}
}
}
}
//prepare the updated cost for the next iteration
for (int i = 1; i <= N; i++)
best_cost_prev[i] = best_cost_new[i];
//if the sink was reached, there is a path from source to sink
//the path is the shortest, due to the bellman-ford algorithm
if (parent_edges[D] != 0)
{
// we have a path from source to sink
// update the residual graph
//
// parse the path we have found from sink to source, via parent edges
// and find the minimum capacity
int min_capacity = parent_edges[D]->c + 1;
int node = D;
while (node != S)
{
Edge* e = parent_edges[node];
min_capacity = min(min_capacity, e->c);
node = e->u;
}
//increment the flow value
max_flow += min_capacity;
//update the capacity of edges in the residual graph
node = D;
while (node != S)
{
Edge* e = parent_edges[node];
e->c -= min_capacity;
//also update the reverse edge
e->re->c += min_capacity;
node = e->u;
}
}
else
has_s2t_path = false; //no more paths from s to t
}
return max_flow;
}
}
//int e_032_max_flow_min_dijsktra_matrices()
int main()
{
using namespace e_032_max_flow_min_dijsktra_matrices_nms;
string in_file = "fmcm.in";
string out_file = "fmcm.out";
int N, M, S, D;
vector<vector<Edge*>> adj_list;
ifstream ifs(in_file.c_str());
if (!ifs.is_open())
{
cout << "Input file not found" << endl;
return -1; // no input file
}
ifs >> N >> M >> S >> D;
adj_list.resize(N + 1);
for (int m = 1; m <= M; m++)
{
//create the forward and it's backward edge
Edge* e = new Edge;
Edge* re = new Edge;
ifs >> e->u >> e->v >> e->c >> e->z;
e->dir = 1;
e->re = re;
re->u = e->v;
re->v = e->u;
re->c = 0;
re->z = -e->z;
re->dir = -1;
re->re = e;
adj_list[e->u].push_back(e);
adj_list[e->v].push_back(re);
}
ifs.close();
find_max_flow_ford_fulkerson(N, S, D, adj_list);
//find the cost of the flow
int total_cost = 0;
for (int u = 1; u <= N; u++)
{
for (auto e : adj_list[u])
{
// the flow of the edge is the capacity of the forward edge minus
// the capacity of the backward edge
if (e->dir == 1)
{
int flow_e = e->re->c;
//if the edge has flow, add the cost of the edge to the total cost
total_cost += flow_e * e->z;
}
}
}
ofstream ofs(out_file.c_str());
//ofs << max_flow << ", " << total_cost;
ofs << total_cost;
ofs.close();
//release the memory
for (int u = 1; u <= N; u++)
for (vector<Edge*>::iterator it = adj_list[u].begin(); it != adj_list[u].end(); it++)
delete *it;
return 0;
}