Cod sursa(job #2461151)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 24 septembrie 2019 22:11:49
Problema Flux maxim de cost minim Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.77 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("fmcm.in");
ofstream fout("fmcm.out");

const int dim = 355;
const int inf = 1000000000;

struct Data {
	int node, cost;
	Data() {}
	Data(int node, int cost) {
		this->node = node;
		this->cost = cost;
	}
};

struct Comp {
	bool operator()(const Data &a, const Data &b) {
		return a.cost > b.cost;
	}
};

priority_queue< Data, vector< Data >, Comp > heap;

int n;

vector<int> graph[dim];

int cost[dim][dim], capacity[dim][dim], flow[dim][dim];

int dist[dim], newDist[dim], dp[dim], parent[dim];

queue<int> que;
bool inQue[dim];
void bellmanFord(int source, int destination) {

	for (int i = 1; i <= n; ++i)
		dist[i] = inf, inQue[i] = false;

	dist[source] = 0;
	que.push(source);

	while (!que.empty()) {

		int node = que.front();
		inQue[node] = false;

		for (vector<int>::iterator adj = graph[node].begin(); adj != graph[node].end(); ++adj) {

			if (dist[*adj] <= dist[node] + cost[node][*adj] || capacity[node][*adj] == flow[node][*adj])
				continue;

			dist[*adj] = dist[node] + cost[node][*adj];

			if (!inQue[*adj]) {

				inQue[*adj] = true;
				que.push(*adj);

			}

		}

		que.pop();

	}

}

bool dijkstra(int source, int destination) {

	for (int i = 1; i <= n; ++i)
		dp[i] = inf, newDist[i] = inf;

	dp[source] = newDist[source] = 0;

	heap.push(Data(source, 0));

	while (!heap.empty()) {

		int node = heap.top().node;
		int cst = heap.top().cost;

		heap.pop();

		if (cst != dp[node])
			continue;

		for (vector<int>::iterator adj = graph[node].begin(); adj != graph[node].end(); ++adj) {

			if (flow[node][*adj] == capacity[node][*adj])
				continue;

			int temp = dp[node] + cost[node][*adj] - dist[*adj] + dist[node];

			if (temp >= dp[*adj])
				continue;

			dp[*adj] = temp;
			newDist[*adj] = newDist[node] + cost[node][*adj];
			parent[*adj] = node;

			heap.push(Data(*adj, temp));

		}

	}

	// memcpy(dist, newDist, sizeof dist);

	return (dp[destination] != inf);

}

int main() {

	int m, source, destination;
	fin >> n >> m >> source >> destination;

	for (int i = 1; i <= m; ++i) {

		int x, y, cpcty, cst;
		fin >> x >> y >> cpcty >> cst;

		graph[x].push_back(y);
		graph[y].push_back(x);

		capacity[x][y] = cpcty;

		cost[x][y] = cst;
		cost[y][x] = -cst;

	}

	bellmanFord(source, destination);

	int minCost = 0;
	while (dijkstra(source, destination)) {

		int addFlow = inf;

		for (int i = destination; i != source; i = parent[i])
			addFlow = min(addFlow, capacity[parent[i]][i] - flow[parent[i]][i]);

		minCost += addFlow * dist[destination];

		for (int i = destination; i != source; i = parent[i]) {

			flow[parent[i]][i] += addFlow;
			flow[i][parent[i]] -= addFlow;

		}

	}

	fout << minCost << '\n';

	return 0;

}

//Trust me, I'm the Doctor!