fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. const ll INF = 4e18; // large number for costs / flows
  6.  
  7. // =====================================================================
  8. // This file contains a collection of Minimum Cost Maximum Flow (MCMF)
  9. // and related Network Flow algorithms. Each function is ready to be used
  10. // as a "black box".
  11. // Read the comments above each one to understand:
  12. //   - What it solves
  13. //   - What input it expects
  14. //   - What it returns
  15. //   - Time complexity
  16. //   - Important constraints / assumptions
  17. // =====================================================================
  18.  
  19. // =====================================================================
  20. // 1) STANDARD MIN-COST MAX-FLOW (MCMF) WITH SPFA
  21. //    Safest and simplest. Handles negative edge costs.
  22. //    Use when graph is small or costs are negative.
  23. // =====================================================================
  24.  
  25. struct MCMF_SPFA {
  26.     struct Edge {
  27.         int to, rev;   // destination, index of reverse edge
  28.         int cap;       // remaining capacity
  29.         ll cost;       // cost per unit of flow
  30.     };
  31.  
  32.     int n;
  33.     vector<vector<Edge>> adj;
  34.  
  35.     MCMF_SPFA(int n) : n(n), adj(n) {}
  36.  
  37.     // Adds a directed edge u->v with given capacity and cost.
  38.     // Also adds the reverse edge (cap 0, cost -cost).
  39.     void addEdge(int u, int v, int cap, ll cost) {
  40.         Edge a{v, (int)adj[v].size(), cap, cost};
  41.         Edge b{u, (int)adj[u].size(), 0, -cost};
  42.         adj[u].push_back(a);
  43.         adj[v].push_back(b);
  44.     }
  45.  
  46.     // Sends flow from s to t while minimizing total cost.
  47.     // If maxf == 0, sends as much as possible.
  48.     // Returns pair {flow, cost}.
  49.     // Complexity: O(flow * E * V) worst-case, but usually O(flow * E).
  50.     // Precondition: no negative cost cycles reachable from s.
  51.     pair<int, ll> minCostMaxFlow(int s, int t, int maxf = 0) {
  52.         int flow = 0;
  53.         ll cost = 0;
  54.  
  55.         while (true) {
  56.             vector<ll> dist(n, INF);
  57.             vector<int> pv(n, -1), pe(n, -1);
  58.             vector<bool> inq(n, false);
  59.             queue<int> q;
  60.  
  61.             dist[s] = 0;
  62.             q.push(s);
  63.             inq[s] = true;
  64.  
  65.             while (!q.empty()) {
  66.                 int u = q.front(); q.pop();
  67.                 inq[u] = false;
  68.                 for (int i = 0; i < (int)adj[u].size(); i++) {
  69.                     Edge &e = adj[u][i];
  70.                     if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
  71.                         dist[e.to] = dist[u] + e.cost;
  72.                         pv[e.to] = u;
  73.                         pe[e.to] = i;
  74.                         if (!inq[e.to]) {
  75.                             q.push(e.to);
  76.                             inq[e.to] = true;
  77.                         }
  78.                     }
  79.                 }
  80.             }
  81.  
  82.             if (dist[t] == INF) break;
  83.  
  84.             int add = (maxf == 0) ? INT_MAX : maxf;
  85.             for (int v = t; v != s; v = pv[v]) {
  86.                 add = min(add, adj[pv[v]][pe[v]].cap);
  87.             }
  88.             if (maxf != 0 && flow + add > maxf) add = maxf - flow;
  89.  
  90.             for (int v = t; v != s; v = pv[v]) {
  91.                 Edge &e = adj[pv[v]][pe[v]];
  92.                 e.cap -= add;
  93.                 adj[v][e.rev].cap += add;
  94.                 cost += (ll)add * e.cost;
  95.             }
  96.             flow += add;
  97.  
  98.             if (maxf != 0 && flow == maxf) break;
  99.         }
  100.         return {flow, cost};
  101.     }
  102. };
  103.  
  104. // =====================================================================
  105. // 2) MIN-COST MAX-FLOW WITH DIJKSTRA + POTENTIALS (FAST)
  106. //    Use this for large graphs. Handles negative costs via initial SPFA.
  107. //    Complexity: O(flow * E log V).
  108. // =====================================================================
  109.  
  110. struct MCMF_Dijkstra {
  111.     struct Edge {
  112.         int to, rev, cap;
  113.         ll cost;
  114.     };
  115.  
  116.     int n;
  117.     vector<vector<Edge>> adj;
  118.     vector<ll> pot; // Johnson potentials
  119.  
  120.     MCMF_Dijkstra(int n) : n(n), adj(n), pot(n, 0) {}
  121.  
  122.     void addEdge(int u, int v, int cap, ll cost) {
  123.         Edge a{v, (int)adj[v].size(), cap, cost};
  124.         Edge b{u, (int)adj[u].size(), 0, -cost};
  125.         adj[u].push_back(a);
  126.         adj[v].push_back(b);
  127.     }
  128.  
  129.     // Sends flow from s to t with minimum cost.
  130.     // If maxf == 0, sends as much as possible.
  131.     // Returns {flow, cost}.
  132.     // Precondition: no negative cost cycles.
  133.     pair<int, ll> minCostMaxFlow(int s, int t, int maxf = 0) {
  134.         const ll INFLL = INF;
  135.         int flow = 0;
  136.         ll cost = 0;
  137.  
  138.         // Initial potentials via SPFA (handles negative edges safely)
  139.         vector<ll> dist(n, INFLL);
  140.         vector<bool> inq(n, false);
  141.         queue<int> q;
  142.         dist[s] = 0;
  143.         q.push(s);
  144.         inq[s] = true;
  145.  
  146.         while (!q.empty()) {
  147.             int u = q.front(); q.pop();
  148.             inq[u] = false;
  149.             for (auto &e : adj[u]) {
  150.                 if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
  151.                     dist[e.to] = dist[u] + e.cost;
  152.                     if (!inq[e.to]) {
  153.                         q.push(e.to);
  154.                         inq[e.to] = true;
  155.                     }
  156.                 }
  157.             }
  158.         }
  159.  
  160.         for (int i = 0; i < n; i++) {
  161.             if (dist[i] < INFLL) pot[i] = dist[i];
  162.         }
  163.  
  164.         while (true) {
  165.             fill(dist.begin(), dist.end(), INFLL);
  166.             vector<int> pv(n, -1), pe(n, -1);
  167.             priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  168.  
  169.             dist[s] = 0;
  170.             pq.push({0, s});
  171.  
  172.             while (!pq.empty()) {
  173.                 auto [d, u] = pq.top(); pq.pop();
  174.                 if (d != dist[u]) continue;
  175.  
  176.                 for (int i = 0; i < (int)adj[u].size(); i++) {
  177.                     Edge &e = adj[u][i];
  178.                     if (e.cap <= 0) continue;
  179.  
  180.                     ll nd = d + e.cost + pot[u] - pot[e.to];
  181.                     if (dist[e.to] > nd) {
  182.                         dist[e.to] = nd;
  183.                         pv[e.to] = u;
  184.                         pe[e.to] = i;
  185.                         pq.push({nd, e.to});
  186.                     }
  187.                 }
  188.             }
  189.  
  190.             if (dist[t] == INFLL) break;
  191.  
  192.             for (int i = 0; i < n; i++) {
  193.                 if (dist[i] < INFLL) pot[i] += dist[i];
  194.             }
  195.  
  196.             int add = (maxf == 0) ? INT_MAX : maxf;
  197.             for (int v = t; v != s; v = pv[v]) {
  198.                 add = min(add, adj[pv[v]][pe[v]].cap);
  199.             }
  200.             if (maxf != 0 && flow + add > maxf) add = maxf - flow;
  201.  
  202.             for (int v = t; v != s; v = pv[v]) {
  203.                 Edge &e = adj[pv[v]][pe[v]];
  204.                 e.cap -= add;
  205.                 adj[v][e.rev].cap += add;
  206.                 cost += (ll)add * e.cost;
  207.             }
  208.             flow += add;
  209.  
  210.             if (maxf != 0 && flow == maxf) break;
  211.         }
  212.         return {flow, cost};
  213.     }
  214. };
  215.  
  216. // =====================================================================
  217. // 3) MAX FLOW (DINIC)
  218. //    Use when only maximum flow is needed (no costs).
  219. //    Complexity: O(E * V^2) worst-case, but fast in practice.
  220. // =====================================================================
  221.  
  222. struct Dinic {
  223.     struct Edge {
  224.         int to, rev, cap;
  225.     };
  226.  
  227.     int n;
  228.     vector<vector<Edge>> adj;
  229.     vector<int> level, ptr;
  230.  
  231.     Dinic(int n) : n(n), adj(n), level(n), ptr(n) {}
  232.  
  233.     void addEdge(int u, int v, int cap) {
  234.         Edge a{v, (int)adj[v].size(), cap};
  235.         Edge b{u, (int)adj[u].size(), 0};
  236.         adj[u].push_back(a);
  237.         adj[v].push_back(b);
  238.     }
  239.  
  240.     bool bfs(int s, int t) {
  241.         fill(level.begin(), level.end(), -1);
  242.         queue<int> q;
  243.         level[s] = 0;
  244.         q.push(s);
  245.         while (!q.empty()) {
  246.             int u = q.front(); q.pop();
  247.             for (auto &e : adj[u]) {
  248.                 if (e.cap > 0 && level[e.to] == -1) {
  249.                     level[e.to] = level[u] + 1;
  250.                     q.push(e.to);
  251.                 }
  252.             }
  253.         }
  254.         return level[t] != -1;
  255.     }
  256.  
  257.     int dfs(int u, int t, int pushed) {
  258.         if (pushed == 0) return 0;
  259.         if (u == t) return pushed;
  260.         for (int &cid = ptr[u]; cid < (int)adj[u].size(); cid++) {
  261.             Edge &e = adj[u][cid];
  262.             if (e.cap <= 0 || level[e.to] != level[u] + 1) continue;
  263.             int tr = dfs(e.to, t, min(pushed, e.cap));
  264.             if (tr == 0) continue;
  265.             e.cap -= tr;
  266.             adj[e.to][e.rev].cap += tr;
  267.             return tr;
  268.         }
  269.         return 0;
  270.     }
  271.  
  272.     int maxFlow(int s, int t) {
  273.         int flow = 0;
  274.         while (bfs(s, t)) {
  275.             fill(ptr.begin(), ptr.end(), 0);
  276.             while (int pushed = dfs(s, t, INT_MAX)) {
  277.                 flow += pushed;
  278.             }
  279.         }
  280.         return flow;
  281.     }
  282. };
  283.  
  284. // =====================================================================
  285. // 4) HUNGARIAN ALGORITHM (ASSIGNMENT PROBLEM)
  286. //    Solves min-cost perfect matching for n rows and m columns (n <= m).
  287. //    If n > m, it transposes the matrix (each column gets matched to a row).
  288. //    Complexity: O(n^2 * m).
  289. // =====================================================================
  290.  
  291. // Returns {minCost, assignment} where assignment[i] = column assigned to row i.
  292. // If n > m, some rows may have assignment = -1 (meaning unmatched).
  293. pair<ll, vector<int>> hungarian(const vector<vector<ll>> &a) {
  294.     int n = (int)a.size();
  295.     int m = (int)a[0].size();
  296.  
  297.     // If more rows than columns, transpose so that rows <= columns.
  298.     if (n > m) {
  299.         vector<vector<ll>> trans(m, vector<ll>(n));
  300.         for (int i = 0; i < n; i++)
  301.             for (int j = 0; j < m; j++)
  302.                 trans[j][i] = a[i][j];
  303.         auto res = hungarian(trans); // res.second has size m (original columns)
  304.         vector<int> origAssign(n, -1);
  305.         for (int j = 0; j < m; j++) {
  306.             int row = res.second[j]; // original row matched to column j
  307.             origAssign[row] = j;
  308.         }
  309.         return {res.first, origAssign};
  310.     }
  311.  
  312.     // Standard Hungarian for n <= m
  313.     vector<ll> u(n + 1), v(m + 1), p(m + 1), way(m + 1);
  314.     for (int i = 1; i <= n; i++) {
  315.         p[0] = i;
  316.         int j0 = 0;
  317.         vector<ll> minv(m + 1, INF);
  318.         vector<bool> used(m + 1, false);
  319.         do {
  320.             used[j0] = true;
  321.             int i0 = p[j0];
  322.             ll delta = INF;
  323.             int j1 = 0;
  324.             for (int j = 1; j <= m; j++) {
  325.                 if (!used[j]) {
  326.                     ll cur = a[i0 - 1][j - 1] - u[i0] - v[j];
  327.                     if (cur < minv[j]) {
  328.                         minv[j] = cur;
  329.                         way[j] = j0;
  330.                     }
  331.                     if (minv[j] < delta) {
  332.                         delta = minv[j];
  333.                         j1 = j;
  334.                     }
  335.                 }
  336.             }
  337.             for (int j = 0; j <= m; j++) {
  338.                 if (used[j]) {
  339.                     u[p[j]] += delta;
  340.                     v[j] -= delta;
  341.                 } else {
  342.                     minv[j] -= delta;
  343.                 }
  344.             }
  345.             j0 = j1;
  346.         } while (p[j0] != 0);
  347.  
  348.         do {
  349.             int j1 = way[j0];
  350.             p[j0] = p[j1];
  351.             j0 = j1;
  352.         } while (j0);
  353.     }
  354.  
  355.     vector<int> assignment(n);
  356.     for (int j = 1; j <= m; j++) {
  357.         if (p[j] > 0) assignment[p[j] - 1] = j - 1;
  358.     }
  359.     ll cost = -v[0];
  360.     return {cost, assignment};
  361. }
  362.  
  363. // =====================================================================
  364. // 5) MIN-COST FLOW WITH LOWER BOUNDS
  365. //    Some edges must carry at least 'low' units. Finds min-cost circulation
  366. //    with an optional s-t flow requirement.
  367. // =====================================================================
  368.  
  369. // edges: (u, v, low, high, cost)
  370. // Returns {flowSent, totalCost}. If infeasible, returns {-1, -1}.
  371. // 'flowSent' is the amount of flow on the t->s edge (i.e., the s-t flow).
  372. pair<int, ll> minCostFlowWithLowerBounds(
  373.     int n,
  374.     vector<tuple<int, int, int, int, ll>> edges, // u, v, low, high, cost
  375.     int s, int t,
  376.     int req = 0          // required s-t flow; 0 means any
  377. ) {
  378.     int SS = n, TT = n + 1;
  379.     MCMF_Dijkstra mcmf(n + 2);
  380.  
  381.     vector<ll> demand(n, 0);
  382.     ll baseCost = 0;
  383.  
  384.     // Add edges with adjusted capacities and accumulate demands
  385.     for (auto &[u, v, low, high, cost] : edges) {
  386.         demand[u] -= low;
  387.         demand[v] += low;
  388.         baseCost += low * cost;
  389.         mcmf.addEdge(u, v, high - low, cost);
  390.     }
  391.  
  392.     // Add t->s edge with capacity = req (or INF if req==0)
  393.     int capTS = (req == 0) ? INT_MAX : req;
  394.     int idxTS = (int)mcmf.adj[t].size(); // forward edge index in adj[t]
  395.     mcmf.addEdge(t, s, capTS, 0);
  396.  
  397.     // Add super source/sink edges based on demands
  398.     ll totalDemand = 0;
  399.     for (int i = 0; i < n; i++) {
  400.         if (demand[i] > 0) {
  401.             mcmf.addEdge(SS, i, (int)demand[i], 0);
  402.             totalDemand += demand[i];
  403.         } else if (demand[i] < 0) {
  404.             mcmf.addEdge(i, TT, (int)(-demand[i]), 0);
  405.         }
  406.     }
  407.  
  408.     // Run MCMF from SS to TT, send as much as possible
  409.     auto [flow, cost] = mcmf.minCostMaxFlow(SS, TT, 0);
  410.  
  411.     if (flow != totalDemand) {
  412.         return {-1, -1}; // infeasible
  413.     }
  414.  
  415.     // Compute actual flow on t->s edge
  416.     int flowOnTS = capTS - mcmf.adj[t][idxTS].cap;
  417.     return {flowOnTS, cost + baseCost};
  418. }
  419.  
  420. // =====================================================================
  421. // 6) HELPER FUNCTIONS FOR COMMON PATTERNS
  422. // =====================================================================
  423.  
  424. // 6.1) MIN-COST FLOW WITH VERTEX CAPACITIES (NODE SPLITTING)
  425. //      Each node can handle at most vertexCap[i] units of flow.
  426. //      If vertexCap[i] == 0, it means infinite.
  427. //      Returns {flow, cost}.
  428. pair<int, ll> minCostFlowWithVertexCaps(
  429.     int n,
  430.     vector<tuple<int, int, int, ll>> edges, // (u, v, cap, cost)
  431.     vector<int> vertexCap,                  // size n
  432.     int s, int t,
  433.     int maxFlow = 0
  434. ) {
  435.     int N = 2 * n + 2;
  436.     int SS = 2 * n;
  437.     int TT = 2 * n + 1;
  438.     MCMF_Dijkstra mcmf(N);
  439.  
  440.     // Vertex capacity edges: in(v) -> out(v)
  441.     for (int v = 0; v < n; v++) {
  442.         int cap = (vertexCap[v] == 0) ? INT_MAX / 2 : vertexCap[v];
  443.         mcmf.addEdge(2 * v, 2 * v + 1, cap, 0);
  444.     }
  445.  
  446.     // Original edges: out(u) -> in(v)
  447.     for (auto &[u, v, cap, cost] : edges) {
  448.         mcmf.addEdge(2 * u + 1, 2 * v, cap, cost);
  449.     }
  450.  
  451.     // Super source -> s_in, t_out -> super sink
  452.     int req = (maxFlow == 0) ? INT_MAX / 2 : maxFlow;
  453.     mcmf.addEdge(SS, 2 * s, req, 0);
  454.     mcmf.addEdge(2 * t + 1, TT, req, 0);
  455.  
  456.     auto [flow, cost] = mcmf.minCostMaxFlow(SS, TT, maxFlow);
  457.     return {flow, cost};
  458. }
  459.  
  460. // 6.2) MULTI-SOURCE / MULTI-SINK MIN-COST FLOW
  461. //      Sources have supplies, sinks have demands.
  462. //      Returns {flow, cost}.
  463. pair<int, ll> multiSourceSinkMCMF(
  464.     int n,
  465.     vector<tuple<int, int, int, ll>> edges,
  466.     vector<pair<int, int>> sources, // (node, supply)
  467.     vector<pair<int, int>> sinks,   // (node, demand)
  468.     int maxFlow = 0
  469. ) {
  470.     int SS = n, TT = n + 1;
  471.     MCMF_Dijkstra mcmf(n + 2);
  472.  
  473.     for (auto &[u, v, cap, cost] : edges) {
  474.         mcmf.addEdge(u, v, cap, cost);
  475.     }
  476.  
  477.     ll totalSupply = 0;
  478.     for (auto &[node, supply] : sources) {
  479.         mcmf.addEdge(SS, node, supply, 0);
  480.         totalSupply += supply;
  481.     }
  482.  
  483.     ll totalDemand = 0;
  484.     for (auto &[node, demand] : sinks) {
  485.         mcmf.addEdge(node, TT, demand, 0);
  486.         totalDemand += demand;
  487.     }
  488.  
  489.     int req = (maxFlow == 0) ? (int)min(totalSupply, totalDemand) : maxFlow;
  490.     auto [flow, cost] = mcmf.minCostMaxFlow(SS, TT, req);
  491.     return {flow, cost};
  492. }
  493.  
  494. // 6.3) MAX PROFIT FLOW (negate profits and run MCMF)
  495. pair<int, ll> maxProfitFlow(
  496.     int n,
  497.     vector<tuple<int, int, int, ll>> edges, // (u, v, cap, profit)
  498.     int s, int t,
  499.     int maxFlow = 0
  500. ) {
  501.     vector<tuple<int, int, int, ll>> costEdges;
  502.     for (auto &[u, v, cap, profit] : edges) {
  503.         costEdges.emplace_back(u, v, cap, -profit);
  504.     }
  505.     MCMF_Dijkstra mcmf(n);
  506.     for (auto &[u, v, cap, cost] : costEdges) {
  507.         mcmf.addEdge(u, v, cap, cost);
  508.     }
  509.     auto [flow, minCost] = mcmf.minCostMaxFlow(s, t, maxFlow);
  510.     return {flow, -minCost};
  511. }
  512.  
  513. // 6.4) MAXIMUM WEIGHT BIPARTITE MATCHING (dense)
  514. //      Uses Hungarian after negating profits.
  515. //      Returns {maxProfit, assignment} (assignment may have -1 for unmatched rows).
  516. pair<ll, vector<int>> maxWeightBipartiteMatching(const vector<vector<ll>>& profitMatrix) {
  517.     int n = profitMatrix.size();
  518.     int m = profitMatrix[0].size();
  519.     vector<vector<ll>> costMatrix(n, vector<ll>(m));
  520.     for (int i = 0; i < n; i++)
  521.         for (int j = 0; j < m; j++)
  522.             costMatrix[i][j] = -profitMatrix[i][j];
  523.     auto [minCost, assignment] = hungarian(costMatrix);
  524.     return {-minCost, assignment};
  525. }
  526.  
  527. // 6.5) MINIMUM PATH COVER IN A DAG (unweighted)
  528. //      Returns the minimum number of vertex-disjoint paths covering all nodes.
  529. int minPathCoverCount(int n, const vector<pair<int, int>>& dagEdges) {
  530.     int total = 2 * n + 2;
  531.     int S = 2 * n, T = 2 * n + 1;
  532.     Dinic dinic(total);
  533.  
  534.     for (int i = 0; i < n; i++) {
  535.         dinic.addEdge(S, i, 1);
  536.         dinic.addEdge(n + i, T, 1);
  537.     }
  538.     for (auto &[u, v] : dagEdges) {
  539.         dinic.addEdge(u, n + v, 1);
  540.     }
  541.  
  542.     int maxMatching = dinic.maxFlow(S, T);
  543.     return n - maxMatching;
  544. }
  545.  
  546. // 6.6) MINIMUM COST PATH COVER IN A DAG (weighted)
  547. //      Returns {numberOfPaths, minTotalCost}.
  548. pair<int, ll> minCostPathCover(int n, const vector<tuple<int, int, ll>>& dagEdges) {
  549.     int S = 2 * n, T = 2 * n + 1;
  550.     MCMF_Dijkstra mcmf(2 * n + 2);
  551.  
  552.     for (int i = 0; i < n; i++) {
  553.         mcmf.addEdge(S, i, 1, 0);
  554.         mcmf.addEdge(n + i, T, 1, 0);
  555.     }
  556.     for (auto &[u, v, cost] : dagEdges) {
  557.         mcmf.addEdge(u, n + v, 1, cost);
  558.     }
  559.  
  560.     auto [flow, cost] = mcmf.minCostMaxFlow(S, T, 0);
  561.     int paths = n - flow;
  562.     return {paths, cost};
  563. }
  564.  
  565. // =====================================================================
  566. // EXAMPLE USAGE (remove in production)
  567. // =====================================================================
  568.  
  569. int main() {
  570.     ios::sync_with_stdio(false);
  571.     cin.tie(nullptr);
  572.  
  573.     // Example 1: Basic MCMF (SPFA)
  574.     MCMF_SPFA mcmf1(4);
  575.     mcmf1.addEdge(0, 1, 10, 2);
  576.     mcmf1.addEdge(0, 2, 10, 3);
  577.     mcmf1.addEdge(1, 3, 5, 1);
  578.     mcmf1.addEdge(2, 3, 10, 4);
  579.     auto res1 = mcmf1.minCostMaxFlow(0, 3);
  580.     cout << "SPFA MCMF: Flow=" << res1.first << ", Cost=" << res1.second << "\n";
  581.  
  582.     // Example 2: Hungarian
  583.     vector<vector<ll>> costMatrix = {
  584.         {4, 1, 3},
  585.         {2, 0, 5},
  586.         {3, 2, 2}
  587.     };
  588.     auto res2 = hungarian(costMatrix);
  589.     cout << "Hungarian: Min Cost=" << res2.first << "\nAssignment: ";
  590.     for (int x : res2.second) cout << x << " ";
  591.     cout << "\n";
  592.  
  593.     // Example 3: Dinic max flow
  594.     Dinic dinic(4);
  595.     dinic.addEdge(0, 1, 10);
  596.     dinic.addEdge(0, 2, 10);
  597.     dinic.addEdge(1, 3, 5);
  598.     dinic.addEdge(2, 3, 10);
  599.     cout << "Dinic Max Flow: " << dinic.maxFlow(0, 3) << "\n";
  600.  
  601.     return 0;
  602. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
SPFA MCMF: Flow=15, Cost=85
Hungarian: Min Cost=5
Assignment: 1 0 2 
Dinic Max Flow: 15
https://ideone.com/66gsTH
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!