Cod sursa(job #677583)

Utilizator Data 10 februarie 2012 12:49:36 Flux maxim de cost minim 50 cpp done Arhiva educationala 3.47 kb
``````#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>

using namespace std;

const int oo = 0x3f3f3f3f;
const double eps = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define FORD(i,a,b) for (int i = int(b)-1; i >= (a); i--)
#define FORIT(i,c) for (list<Edge>::iterator i = (c).begin(); i != (c).end(); i++)

struct Edge {
int to, residual, cost;
bool orig;
list<Edge>::iterator rev;
int len;

};

struct Node {
int dist, pot;
list<Edge>::iterator prev;
list<Edge> out;
};

const int MAXN = 355;
int N, S, T;

Node nodes[MAXN];

void reset(int n, int s, int t) {
N = n; S = s; T = t;
FOR(i, 0, MAXN) nodes[i].out.clear();
}

void add_edge(int a, int b, int cap, int cost) {
Edge ab = {b, cap, cost, true}, ba = {a, 0, -cost, false};
nodes[a].out.push_front(ab);
list<Edge>::iterator e = nodes[a].out.begin();
nodes[b].out.push_front(ba);
e->rev = nodes[b].out.begin(), nodes[b].out.begin()->rev = e;
}

void init_pots() {
FOR(i, 0, N) nodes[i].pot = 0;
FOR(i, 0, N) FOR(j, 0, N) FORIT(it, nodes[j].out) if (it->orig) {
nodes[it->to].pot = min(nodes[it->to].pot, nodes[j].pot + it->cost);
}
}

void dijkstra(int start) {
FOR(i, 0, N) nodes[i].dist = INT_MAX;
nodes[start].dist = 0;
set<pii> pq;
pq.insert(pii(0, start));
while (!pq.empty()) {
int cur = pq.begin()->second;
pq.erase(pq.begin());
FORIT(i, nodes[cur].out) {
if (i->residual == 0) continue;
if (nodes[cur].dist + i->len >= nodes[i->to].dist) continue;
if (nodes[i->to].dist < INT_MAX) pq.erase(pq.find(pii(nodes[i->to].dist, i->to)));
nodes[i->to].dist = nodes[cur].dist + i->len;
nodes[i->to].prev = i->rev;
pq.insert(pii(nodes[i->to].dist, i->to));
}
}
}

int augment(int n, int cap, int &cost) {
if (n == S) return cap;
cap = augment(nodes[n].prev->to, min(cap, nodes[n].prev->rev->residual), cost);
nodes[n].prev->rev->residual -= cap;
nodes[n].prev->residual += cap;
cost += cap * nodes[n].prev->rev->cost;
return cap;
}

void mcmf() {
//Netzwerk initialisieren mit reset und add_edge

int n, m, s, d;

scanf ("%d %d %d %d", &n, &m, &s, &d);

--s;
--d;
reset (n, s, d);
FOR (i, 0, m) {
int x, y, cap, cost;

scanf ("%d %d %d %d", &x, &y, &cap, &cost);
--x, --y;
add_edge(x, y, cap, cost);
}

init_pots();

int flow = 0, cost = 0;

while (1) {
FOR(i, 0, N) FORIT(it, nodes[i].out) {
it->len = it->cost + nodes[i].pot - nodes[it->to].pot;
}

dijkstra(S);

if (nodes[T].dist == INT_MAX) break;
flow += augment(T, INT_MAX, cost);
FOR(i, 0, N) nodes[i].pot += nodes[i].dist;
}

printf ("%d\n", cost);
}

int main () {
freopen ("fmcm.in", "r", stdin);
freopen ("fmcm.out", "w", stdout);

mcmf();

return 0;
}``````