Cod sursa(job #816255)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 17 noiembrie 2012 12:26:10
Problema Flux maxim de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.43 kb
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <vector>

using namespace std;

inline int next_int() {
	int n = 0, sign = 1;
	char c = getchar_unlocked();
	while (!('0' <= c && c <= '9')) {
		sign *= c == '-' ? -1 : 1;
		c = getchar_unlocked();
	}
	while ('0' <= c && c <= '9') {
		n = n * 10 + c - '0';
		c = getchar_unlocked();
	}
	return sign * n;
}

const int INF = 1e9;
const int MAX_V = 350 + 1;
const int MAX_E = 12500 + 12500;

int V, E, min_cost, max_flow, path_cost, path_flow, where, source, sink;
int from[MAX_E], to[MAX_E], capacity[MAX_E], cost[MAX_E], e_begin[MAX_V], e_next[MAX_E], dist[MAX_V], prev[MAX_V];
int heap_size, heap[MAX_V], pos[MAX_V];
bool seen[MAX_V];

inline void add_edge(const int & a, const int & b, const int & c, const int & d) {
	from[E] = a, to[E] = b, capacity[E] = c, cost[E] = +d, E++;
	from[E] = b, to[E] = a, capacity[E] = 0, cost[E] = -d, E++;
}

inline void sw(const int & x, const int & y) {
	swap(heap[x], heap[y]);
	pos[heap[x]] = x;
	pos[heap[y]] = y;
}

inline void run() {
	for (int v = 1; v <= V; v++) {
		dist[v] = INF;
		e_begin[v] = -1;
	}
	dist[source] = 0;
	for (int e = 0; e < E; e++) {
		e_next[e] = e_begin[from[e]];
		e_begin[from[e]] = e;
	}
	for (int v = 1; v <= V; v++) {
		bool done = 1;
		for (int e = 0; e < E; e++) {
			if (dist[from[e]] < INF && capacity[e] > 0 && dist[from[e]] + cost[e] < dist[to[e]]) {
				dist[to[e]] = dist[from[e]] + cost[e];
				done = 0;
			}
		}
		if (done) {
			break;
		}
	}
	path_cost = dist[sink];
	while (true) {
		for (int e = 0; e < E; e++) {
			if (dist[from[e]] < INF && dist[to[e]] < INF) {
				cost[e] += dist[from[e]] - dist[to[e]];
			}
		}
		for (int v = 1; v <= V; v++) {
			prev[v] = -1;
			seen[v] = false;
			dist[v] = INF;
			heap[v] = pos[v] = v;
		}
		heap_size = V;
		dist[source] = 0;
		sw(1, source);
		while (heap_size) {
			int current_where = heap[1];
			int current_dist = dist[current_where];
			sw(1, heap_size);
			heap_size--;
			int mn = 1, n = 0;
			while (mn != n) {
				n = mn;
				if (n << 1 <= heap_size && dist[heap[mn]] > dist[heap[n << 1]]) {
					mn = n << 1;
				}
				if ((n << 1 | 1) <= heap_size && dist[heap[mn]] > dist[heap[n << 1 | 1]]) {
					mn = n << 1 | 1;
				}
				sw(mn, n);
			}
			if (!seen[current_where]) {
				seen[current_where] = true;
				for (int e = e_begin[current_where]; e != -1; e = e_next[e]) {
					if (capacity[e] > 0 && current_dist + cost[e] < dist[to[e]]) {
						dist[to[e]] = current_dist + cost[e];
						prev[to[e]] = e;
						int n = pos[to[e]];
						while (n >> 1 && dist[heap[n >> 1]] > dist[heap[n]]) {
							sw(n, n >> 1);
							n >>= 1;
						}
					}
				}
			}
		}
		if (dist[sink] == INF) {
			break;
		}
		for (where = sink, path_flow = INF; where != source; where = from[prev[where]]) {
			path_flow = min(path_flow, capacity[prev[where]]);
		}
		for (where = sink; where != source; where = from[prev[where]]) {
			capacity[prev[where]] -= path_flow;
			capacity[prev[where] ^ 1] += path_flow;
		}
		path_cost += dist[sink];
		min_cost += path_flow * path_cost;
		max_flow += path_flow;
	}
}

int main() {
	freopen("fmcm.in", "r", stdin);
	freopen("fmcm.out", "w", stdout);
	V = next_int();
	int m = next_int();
	source = next_int();
	sink = next_int();
	for (int i = 0; i < m; i++) {
		int x = next_int();
		int y = next_int();
		int c = next_int();
		int z = next_int();
		add_edge(x, y, c, z);
	}
	run();
	printf("%d\n", min_cost);
	return 0;
}