# Cod sursa(job #631550)

Utilizator Data 8 noiembrie 2011 16:21:20 Flux maxim de cost minim 70 cpp done Arhiva educationala 2.8 kb
``````#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

#define MAXN 355

int N, M, S, D;
int C[MAXN][MAXN], Cst[MAXN][MAXN];
vector<int> con[MAXN];
int F, FCst;

int old_d[MAXN]; char inQ[MAXN];
queue<int> Q;

int d[MAXN], real_d[MAXN], p[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > H;

inline bool dijkstra()
{
memset(d, 0x3f, sizeof(d));
d[S] = 0; real_d[S] = 0;
H.push(make_pair(d[S], S));

for (; !H.empty(); )
{
int cst = H.top().first, nod = H.top().second;
H.pop();
if (d[nod] != cst)
continue;

vector<int> :: iterator it;
for (it = con[nod].begin(); it != con[nod].end(); it++)
if (C[nod][*it])
{
int new_d = d[nod] + Cst[nod][*it] + old_d[nod] - old_d[*it];
if (new_d < d[*it])
{
d[*it] = new_d;
real_d[*it] = real_d[nod] + Cst[nod][*it];
p[*it] = nod;
H.push(make_pair(d[*it], *it));
}
}
}
memcpy(old_d, real_d, sizeof(d));
if (d[D] == 0x3f3f3f3f)
return false;

int Min = 0x3f3f3f3f, curCst = 0;
for (int aux = D; aux != S; aux = p[aux])
Min = min(Min, C[p[aux]][aux]),
curCst += Cst[p[aux]][aux];

F += Min;
FCst += Min * real_d[D];
for (int aux = D; aux != S; aux = p[aux])
C[p[aux]][aux] -= Min,
C[aux][p[aux]] += Min;

return true;
}

inline bool bellmanFord()
{
memset(old_d, 0x3f, sizeof(old_d));
old_d[S] = 0;

for (Q.push(S), inQ[S] = 1; !Q.empty(); Q.pop())
{
vector<int> :: iterator it;
int i = Q.front();
inQ[i] = 0;

for (it = con[i].begin(); it != con[i].end(); it++)
if (C[i][*it])
{
if (old_d[i] + Cst[i][*it] >= old_d[*it])
continue;

old_d[*it] = old_d[i] + Cst[i][*it];
if (inQ[*it])
continue;

inQ[*it] = 1;
Q.push(*it);
}
}

if (old_d[D] == 0x3f3f3f3f)
return false;

return true;
}

int main()
{
freopen("fmcm.in", "rt", stdin);
freopen("fmcm.out", "wt", stdout);

scanf("%d %d %d %d", &N, &M, &S, &D);

for (; M; M--)
{
int x, y;
scanf("%d %d ", &x, &y);
con[x].push_back(y);
con[y].push_back(x);

scanf("%d %d", C[x] + y, Cst[x] + y);
Cst[y][x] = -Cst[x][y];
}

F = FCst = 0;
bellmanFord();
for (; dijkstra(); );

printf("%d\n", FCst);
return 0;
}

``````