# Cod sursa(job #1981527)

Utilizator Data 15 mai 2017 22:13:52 Flux maxim de cost minim 50 cpp done Arhiva educationala 2.36 kb
``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define FOR(i, to) for (int i = 0; i < (to); ++i)
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pair<int, int> > vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
#define Nmax 444
#define inf 101010000
int NRN,rez,d[Nmax],p[Nmax],viz[Nmax],inq[Nmax];
vector<pii> mc;
vi v,f,c, m[Nmax];
queue<int> q;
if(inq[x]) return; inq[x] = viz[x] = 1; q.push(x);
}
inline int pop() {
int x = q.front(); q.pop(); inq[x] = 0; // delete for bfs
return x;
}
inline void reset_stuff(int S) {
for(int i = 0; i <= NRN; ++i) {
viz[i] = inq[i] = 0; d[i] = inf;
} d[S] = 0;
}
inline void addEdge(int x,int y,int cap, int cost) {
NRN = max(NRN,x); NRN = max(NRN,y);
c.pb(cap); v.pb(cost); f.pb(0);
m[x].pb(sz(mc)); mc.pb(mp(x,y));
c.pb(0); f.pb(0); v.pb(-cost);
m[y].pb(sz(mc)); mc.pb(mp(y,x));
}

inline int bfs(int S, int D) {
while(!q.empty()) {
int x = pop(); if(x==D) continue;
for(auto y : m[x]) {
int ve = mc[y].sc;
if(f[y] < c[y] && d[ve] > d[x] + v[y]) {
add(ve); p[ve] = y; d[ve] = d[x] + v[y];
}
}
}
return viz[D];
}
pii update(int S, int D) {
int ret = 0, retc = 0, flux = inf, curr = D;
while(curr!=S) {
int muc = p[curr], par = mc[p[curr]].fs;
if(c[muc] - f[muc] < flux) flux = c[muc] - f[muc];
if(!flux) break; curr = par;
}
curr = D;
while(curr!=S) {
int edg = p[curr], par = mc[p[curr]].fs;
f[edg] += flux; f[edg^1] -= flux; curr = par;
}
ret += flux; retc += flux*d[D]; return mp(ret, retc);
}
pii flow(int S, int D) {
int ret = 0, retc = 0;
while(true) {
if(!bfs(S, D)) break;
pii u = update(S,D); ret += u.fs, retc += u.sc;
}
return mp(ret, retc);
}

int main() {
freopen("fmcm.in","r",stdin);
freopen("fmcm.out","w",stdout);
int N,M,S,D;
scanf("%d%d%d%d",&N,&M,&S,&D);
for(int i = 1; i <= M; ++i) {
int x,y,z,t;
scanf("%d%d%d%d",&x,&y,&z,&t);