fork(1) download
copy 
  1. const int mxN = 55;
  2. const int inf = 2e9;
  3. struct Edgee {
  4.   int to, cost, cap, flow, backEdge;
  5. };
  6. struct MCMF {
  7.   int s, t, n;
  8.   vector<Edgee> g[mxN];
  9.   MCMF(int _s, int _t, int _n) {
  10.     s = _s, t = _t, n = _n;
  11.   }
  12.   void addEdge(int u, int v, int cost, int cap) {
  13.     Edgee e1 = { v, cost, cap, 0, g[v].size() };
  14.     Edgee e2 = { u, -cost, 0, 0, g[u].size() };
  15.     g[u].push_back(e1); g[v].push_back(e2);
  16.   }
  17.   pair<int, int> minCostMaxFlow() {
  18.     int flow = 0, cost = 0;
  19.     vector<int> state(n), from(n), from_edge(n), d(n);
  20.     deque<int> q;
  21.     while (true) {
  22.       for (int i = 0; i < n; i++)
  23.         state[i] = 2, d[i] = inf, from[i] = -1;
  24.       state[s] = 1; q.clear(); q.push_back(s); d[s] = 0;
  25.       while (!q.empty()) {
  26.         int v = q.front(); q.pop_front(); state[v] = 0;
  27.         for (int i = 0; i < (int) g[v].size(); i++) {
  28.           Edgee e = g[v][i];
  29.           if (e.flow >= e.cap || d[e.to] <= d[v] + e.cost)
  30.             continue;
  31.           int to = e.to; d[to] = d[v] + e.cost;
  32.           from[to] = v; from_edge[to] = i;
  33.           if (state[to] == 1) continue;
  34.           if (!state[to] || (!q.empty() && d[q.front()] > d[to]))
  35.             q.push_front(to);
  36.           else q.push_back(to);
  37.           state[to] = 1;
  38.         }
  39.       }
  40.       if (d[t] == inf) break;
  41.       int it = t, addflow = inf;
  42.       while (it != s) {
  43.         addflow = min(addflow,
  44.             g[from[it]][from_edge[it]].cap
  45.             - g[from[it]][from_edge[it]].flow);
  46.         it = from[it];
  47.       }
  48.       it = t;
  49.       while (it != s) {
  50.         g[from[it]][from_edge[it]].flow += addflow;
  51.         g[it][g[from[it]][from_edge[it]].backEdge].flow -= addflow;
  52.         cost += g[from[it]][from_edge[it]].cost * addflow;
  53.         it = from[it];
  54.       }
  55.       flow += addflow;
  56.     }
  57.     return {cost,flow};
  58.   }
  59. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:8:3: error: ‘vector’ does not name a type
   vector<Edgee> g[mxN];
   ^~~~~~
prog.cpp:17:3: error: ‘pair’ does not name a type
   pair<int, int> minCostMaxFlow() {
   ^~~~
prog.cpp: In member function ‘void MCMF::addEdge(int, int, int, int)’:
prog.cpp:13:35: error: ‘g’ was not declared in this scope
     Edgee e1 = { v, cost, cap, 0, g[v].size() };
                                   ^
stdout
copy 
Standard output is empty
https://ideone.com/jQqO6I
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!