fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a collection of Dinic (Maximum Flow) algorithms.
  6. // Each function/class is ready to be used as a "black box".
  7. //
  8. // Read the comments above each one to understand:
  9. //   - What it solves
  10. //   - What input it expects
  11. //   - What it returns
  12. //   - Time complexity
  13. //   - Important constraints / assumptions
  14. //   - Explanation of common terms (Jargon) to make it easy for beginners.
  15. // ===================================================================
  16.  
  17. // ===================================================================
  18. // JARGON / TERMINOLOGY EXPLANATION (Read this first!)
  19. // ===================================================================
  20. // 1. Flow Network: A directed graph where each edge has a "capacity"
  21. //    (maximum amount it can carry). We send "flow" (like water or data)
  22. //    from a "Source" (starting point) to a "Sink" (ending point).
  23. //
  24. // 2. Source (s): The node where the flow originates.
  25. // 3. Sink (t): The node where the flow ends.
  26. // 4. Capacity (cap): The maximum amount of flow that can pass through an edge.
  27. // 5. Reverse Edge (Residual Edge): An artificial edge added by the algorithm
  28. //    that allows it to "undo" or reroute flow if a better path is found later.
  29. // 6. Residual Graph: The original graph plus all the reverse edges.
  30. // 7. Level Graph (BFS Layers): A simplified graph where we only keep edges
  31. //    that go from a node in the current BFS layer to the next layer.
  32. //    This helps the algorithm find the shortest augmenting paths.
  33. // 8. Blocking Flow: Sending as much flow as possible through the current
  34. //    Level Graph before rebuilding it.
  35. // 9. Current Arc Optimization: A trick that remembers which edges have
  36. //    already been completely used (saturated) in the current blocking flow,
  37. //    so we don't waste time checking them again.
  38. // 10. Min Cut: The minimum total capacity of edges we need to remove to
  39. //     completely disconnect the Source from the Sink.
  40. // 11. Saturated Edge: An edge where the remaining capacity (cap) is zero.
  41. // ===================================================================
  42.  
  43. // ===================================================================
  44. // MAIN DINIC CLASS (The core engine)
  45. // ===================================================================
  46. // What it solves:
  47. //   Computes the Maximum Flow in a directed graph.
  48. //
  49. // Input:
  50. //   - Number of nodes (n) in the graph (nodes are 0-indexed).
  51. //
  52. // How to use:
  53. //   1. Create an object: Dinic dinic(number_of_nodes);
  54. //   2. Add edges using addEdge(u, v, capacity).
  55. //   3. Call maxFlow(source, sink) to get the maximum flow value.
  56. //
  57. // Time Complexity:
  58. //   O(E * V^2) in the worst case for general graphs.
  59. //   In practice, it is very fast, especially on sparse graphs.
  60. //   For Bipartite Matching, it runs in O(E * sqrt(V)).
  61. //   NOTE: The "current arc optimization" speeds it up significantly.
  62. //
  63. // Notes:
  64. //   - All capacities and flows are stored as 'long long' to prevent overflow.
  65. //   - If you have an undirected edge, you should call addUndirectedEdge
  66. //     (provided in the Tricks section), or add two directed edges.
  67. //   - The graph is 0-indexed. If your nodes are 1-indexed, subtract 1 from
  68. //     every node index.
  69. // ===================================================================
  70.  
  71. struct Dinic {
  72.     struct Edge {
  73.         int to;          // The node this edge goes to
  74.         int rev;         // Index of the reverse edge in the adjacency list of 'to'
  75.         long long cap;   // Remaining capacity of this edge
  76.     };
  77.  
  78.     int n;                      // Number of nodes
  79.     vector<vector<Edge>> adj;   // Adjacency list
  80.     vector<int> level;          // BFS level of each node
  81.     vector<int> it;             // Pointer for current arc optimization
  82.  
  83.     // Constructor: initializes the graph with 'n' nodes.
  84.     Dinic(int n) : n(n), adj(n), level(n), it(n) {}
  85.  
  86.     // -----------------------------------------------------------------
  87.     // addEdge
  88.     // -----------------------------------------------------------------
  89.     // What it does:
  90.     //   Adds a directed edge from node 'u' to node 'v' with a maximum
  91.     //   capacity 'cap'. Flow can only travel from 'u' to 'v' in the
  92.     //   original network.
  93.     //
  94.     // Input:
  95.     //   u   : source node of the edge
  96.     //   v   : destination node of the edge
  97.     //   cap : maximum capacity of this edge (must be >= 0)
  98.     //
  99.     // Output:
  100.     //   None (modifies the graph internally).
  101.     //
  102.     // Time complexity:
  103.     //   O(1)
  104.     //
  105.     // Notes:
  106.     //   - This automatically adds a reverse edge (with 0 capacity) for
  107.     //     the algorithm to work. You should NOT manually modify or call
  108.     //     this reverse edge directly.
  109.     //   - If cap == 0, the edge is useless but can be safely added.
  110.     // -----------------------------------------------------------------
  111.     void addEdge(int u, int v, long long cap) {
  112.         Edge a{ v, (int)adj[v].size(), cap };
  113.         Edge b{ u, (int)adj[u].size(), 0 };
  114.         adj[u].push_back(a);
  115.         adj[v].push_back(b);
  116.     }
  117.  
  118.     // -----------------------------------------------------------------
  119.     // bfs (Breadth First Search) - Internal helper
  120.     // -----------------------------------------------------------------
  121.     // What it does:
  122.     //   Constructs the "Level Graph" by calculating the shortest distance
  123.     //   (in terms of number of edges) from the source to every other node
  124.     //   using only edges that still have remaining capacity (> 0).
  125.     //
  126.     // Input:
  127.     //   s : the source node
  128.     //   t : the sink node (not strictly needed for BFS, but we stop early if we reach it)
  129.     //
  130.     // Output:
  131.     //   Returns 'true' if the sink 't' is reachable from 's', 'false' otherwise.
  132.     //
  133.     // Time complexity:
  134.     //   O(V + E)
  135.     //
  136.     // Notes:
  137.     //   You don't need to call this manually; it is called inside maxFlow().
  138.     // -----------------------------------------------------------------
  139.     bool bfs(int s, int t) {
  140.         fill(level.begin(), level.end(), -1);
  141.         queue<int> q;
  142.         level[s] = 0;
  143.         q.push(s);
  144.  
  145.         while (!q.empty()) {
  146.             int u = q.front();
  147.             q.pop();
  148.  
  149.             for (const Edge& e : adj[u]) {
  150.                 if (e.cap > 0 && level[e.to] == -1) {
  151.                     level[e.to] = level[u] + 1;
  152.                     if (e.to == t) {
  153.                         // We don't return immediately here to allow full leveling,
  154.                         // but returning early is also safe. We keep standard BFS.
  155.                     }
  156.                     q.push(e.to);
  157.                 }
  158.             }
  159.         }
  160.         return level[t] != -1;
  161.     }
  162.  
  163.     // -----------------------------------------------------------------
  164.     // dfs (Depth First Search) - Internal helper
  165.     // -----------------------------------------------------------------
  166.     // What it does:
  167.     //   Sends as much flow as possible from node 'u' to the sink 't'
  168.     //   using the current Level Graph. It only uses edges that go from
  169.     //   the current BFS layer to the next BFS layer (level[v] == level[u] + 1).
  170.     //
  171.     // Input:
  172.     //   u : current node
  173.     //   t : sink node
  174.     //   f : maximum amount of flow we are allowed to push through this path
  175.     //
  176.     // Output:
  177.     //   Returns the amount of flow actually pushed to the sink.
  178.     //
  179.     // Time complexity:
  180.     //   O(E) per DFS call, but with current arc optimization, total is O(E * V).
  181.     //
  182.     // Notes:
  183.     //   - This is called repeatedly by maxFlow().
  184.     //   - "Current Arc" optimization is implemented using the 'it' pointer.
  185.     //     It remembers which edges are already saturated so we skip them.
  186.     // -----------------------------------------------------------------
  187.     long long dfs(int u, int t, long long f) {
  188.         if (u == t) return f;
  189.  
  190.         for (int &i = it[u]; i < (int)adj[u].size(); i++) {
  191.             Edge &e = adj[u][i];
  192.  
  193.             if (e.cap > 0 && level[e.to] == level[u] + 1) {
  194.                 long long pushed = dfs(e.to, t, min(f, e.cap));
  195.                 if (pushed > 0) {
  196.                     e.cap -= pushed;
  197.                     adj[e.to][e.rev].cap += pushed;
  198.                     return pushed;
  199.                 }
  200.             }
  201.         }
  202.         return 0;
  203.     }
  204.  
  205.     // -----------------------------------------------------------------
  206.     // maxFlow
  207.     // -----------------------------------------------------------------
  208.     // What it solves:
  209.     //   Computes the maximum amount of flow that can be sent from the
  210.     //   'source' node to the 'sink' node in the network.
  211.     //
  212.     // Input:
  213.     //   s : the source node index
  214.     //   t : the sink node index
  215.     //
  216.     // Output:
  217.     //   Returns the total maximum flow value (long long).
  218.     //
  219.     // Time complexity:
  220.     //   O(E * V^2) in the worst case.
  221.     //
  222.     // Constraints:
  223.     //   - Source and sink must be different nodes (s != t).
  224.     //   - All capacities must be non-negative.
  225.     //
  226.     // Notes:
  227.     //   - After this function finishes, the graph will contain the residual
  228.     //     graph. The remaining capacities in the 'adj' list represent
  229.     //     the residual capacities.
  230.     // -----------------------------------------------------------------
  231.     long long maxFlow(int s, int t) {
  232.         long long flow = 0;
  233.         const long long INF = 4e18; // A very large number
  234.  
  235.         while (bfs(s, t)) {
  236.             fill(it.begin(), it.end(), 0);
  237.             while (true) {
  238.                 long long pushed = dfs(s, t, INF);
  239.                 if (pushed == 0) break;
  240.                 flow += pushed;
  241.             }
  242.         }
  243.         return flow;
  244.     }
  245.  
  246.     // -----------------------------------------------------------------
  247.     // getReachableNodes (For Min Cut)
  248.     // -----------------------------------------------------------------
  249.     // What it solves:
  250.     //   After computing the maximum flow, this function finds all nodes
  251.     //   that are still reachable from the 'source' in the residual graph.
  252.     //   The set of these nodes defines the "Source Side" of the minimum cut.
  253.     //
  254.     // Input:
  255.     //   s : the source node index
  256.     //
  257.     // Output:
  258.     //   Returns a vector of booleans (size = n) where 'true' means the node
  259.     //   is reachable from the source in the residual graph.
  260.     //
  261.     // Time complexity:
  262.     //   O(V + E)
  263.     //
  264.     // How to find the Min Cut edges:
  265.     //   Iterate over all original edges (u->v). If reachable[u] is true
  266.     //   and reachable[v] is false, then this edge is part of the minimum cut.
  267.     //
  268.     // Constraints:
  269.     //   - Must be called AFTER running maxFlow(s, t).
  270.     // -----------------------------------------------------------------
  271.     vector<bool> getReachableNodes(int s) {
  272.         vector<bool> reachable(n, false);
  273.         queue<int> q;
  274.         q.push(s);
  275.         reachable[s] = true;
  276.  
  277.         while (!q.empty()) {
  278.             int u = q.front();
  279.             q.pop();
  280.  
  281.             for (const Edge& e : adj[u]) {
  282.                 if (e.cap > 0 && !reachable[e.to]) {
  283.                     reachable[e.to] = true;
  284.                     q.push(e.to);
  285.                 }
  286.             }
  287.         }
  288.         return reachable;
  289.     }
  290. };
  291.  
  292. // ===================================================================
  293. // 1) BIPARTITE MATCHING (Using Max Flow)
  294. // ===================================================================
  295. // What it solves:
  296. //   Given two disjoint sets of nodes (Left and Right), and allowed
  297. //   connections between them, find the maximum number of pairs
  298. //   (one from Left, one from Right) such that each node is used at most once.
  299. //   Example: Assigning workers to jobs.
  300. //
  301. // Input:
  302. //   - n: number of nodes on the Left side (indexed 0..n-1)
  303. //   - m: number of nodes on the Right side (indexed 0..m-1)
  304. //   - edges: a vector of pairs (u, v) meaning Left-node 'u' can connect to Right-node 'v'.
  305. //
  306. // Output:
  307. //   - Returns the maximum number of matches (pairs).
  308. //   - If you need the actual matching pairs, you would need to trace the flow
  309. //     (this function only returns the count).
  310. //
  311. // Time complexity:
  312. //   O(E * sqrt(V)) because Dinic on bipartite graphs is very fast.
  313. //   Where V = n + m + 2 (plus source and sink), E = number of edges.
  314. //
  315. // Constraints:
  316. //   - n, m >= 0.
  317. //   - Node indices must be in the valid ranges.
  318. //
  319. // Notes:
  320. //   - This function builds the flow network internally.
  321. //   - The source is connected to all Left nodes (capacity 1).
  322. //   - Left nodes connect to Right nodes (capacity 1).
  323. //   - Right nodes connect to the sink (capacity 1).
  324. // -----------------------------------------------------------------
  325. int maxBipartiteMatching(int n, int m, const vector<pair<int, int>>& edges) {
  326.     int totalNodes = n + m + 2;
  327.     int source = n + m;
  328.     int sink = source + 1;
  329.  
  330.     Dinic dinic(totalNodes);
  331.  
  332.     // Connect source to left nodes
  333.     for (int u = 0; u < n; u++) {
  334.         dinic.addEdge(source, u, 1);
  335.     }
  336.  
  337.     // Connect left to right
  338.     for (auto [u, v] : edges) {
  339.         // Right nodes are offset by n to avoid index collision with left nodes
  340.         dinic.addEdge(u, n + v, 1);
  341.     }
  342.  
  343.     // Connect right nodes to sink
  344.     for (int v = 0; v < m; v++) {
  345.         dinic.addEdge(n + v, sink, 1);
  346.     }
  347.  
  348.     long long flow = dinic.maxFlow(source, sink);
  349.     return (int)flow;
  350. }
  351.  
  352. // ===================================================================
  353. // 2) MINIMUM PATH COVER IN A DAG (Using Max Flow)
  354. // ===================================================================
  355. // What it solves:
  356. //   Given a Directed Acyclic Graph (DAG), find the minimum number of
  357. //   vertex-disjoint paths needed to cover all vertices.
  358. //   Each vertex belongs to exactly one path.
  359. //
  360. // Input:
  361. //   - n: number of vertices (0-indexed).
  362. //   - edges: a vector of pairs (u, v) representing a directed edge u -> v.
  363. //
  364. // Output:
  365. //   - Returns the minimum number of paths required to cover all nodes.
  366. //
  367. // Time complexity:
  368. //   O(E * sqrt(V)) using Dinic.
  369. //
  370. // Constraint:
  371. //   - The graph must be a DAG (no cycles). If there are cycles, the
  372. //     mathematical reduction doesn't hold.
  373. //   - Paths are vertex-disjoint (no vertex appears in more than one path).
  374. //
  375. // Idea (explained simply):
  376. //   The minimum path cover equals (Total Vertices) - (Maximum Bipartite Matching).
  377. //   We create a bipartite graph where the left side contains all original nodes,
  378. //   and the right side contains copies of all original nodes.
  379. //   For every edge u -> v in the DAG, we add an edge from Left(u) to Right(v).
  380. //   Running max matching gives the maximum number of edges we can "chain"
  381. //   together, which reduces the number of paths.
  382. // -----------------------------------------------------------------
  383. int minPathCoverDAG(int n, const vector<pair<int, int>>& edges) {
  384.     // Build the bipartite graph (Left: 0..n-1, Right: 0..n-1)
  385.     // We reuse the bipartite matching function.
  386.     vector<pair<int, int>> bipEdges;
  387.     for (auto [u, v] : edges) {
  388.         bipEdges.push_back({u, v}); // Left side u, Right side v (both use same indices)
  389.     }
  390.  
  391.     int maxMatch = maxBipartiteMatching(n, n, bipEdges);
  392.     return n - maxMatch;
  393. }
  394.  
  395. // ===================================================================
  396. // TRICKS & ADVANCED PATTERNS (ECPC/ACPC Favorites)
  397. // ===================================================================
  398.  
  399. // 3.1) SUPER SOURCE AND SUPER SINK
  400. // -----------------------------------------------------------------
  401. // What it solves:
  402. //   When you have multiple sources or multiple sinks, you can connect
  403. //   all sources to a single "Super Source" (with INFINITE capacity), and
  404. //   connect all sinks to a single "Super Sink" (with INFINITE capacity).
  405. //
  406. // How to use (Example):
  407. //   int N = ...; int S = N; int T = N+1; // create two new nodes
  408. //   Dinic dinic(N+2);
  409. //   for source in list_of_sources: dinic.addEdge(S, source, INF);
  410. //   for sink in list_of_sinks: dinic.addEdge(sink, T, INF);
  411. //   // Add your normal edges here...
  412. //   long long ans = dinic.maxFlow(S, T);
  413. //
  414. // Input:
  415. //   - You don't call a function for this; it's a pattern.
  416. //   - Just add edges from SuperSource to all sources, and all sinks to SuperSink.
  417. //
  418. // Output:
  419. //   - The result of maxFlow(SuperSource, SuperSink) is the answer.
  420. //
  421. // Notes:
  422. //   - Use INF = 4e18 (or a very large number bigger than any possible flow).
  423. // -----------------------------------------------------------------
  424.  
  425. // 3.2) NODE SPLITTING (Vertex Capacities)
  426. // -----------------------------------------------------------------
  427. // What it solves:
  428. //   By default, only edges have capacities. If you need to limit the
  429. //   amount of flow that passes THROUGH a specific node, you must split it.
  430. //
  431. // How to use (Example):
  432. //   For a node 'v' with capacity 'cap', split it into two nodes:
  433. //   v_in = v * 2, and v_out = v * 2 + 1 (or any other indexing scheme).
  434. //   Add an edge: addEdge(v_in, v_out, cap).
  435. //   For any incoming edge (u -> v), add u_out -> v_in.
  436. //   For any outgoing edge (v -> w), add v_out -> w_in.
  437. //
  438. // Input:
  439. //   - You don't call a function for this; it's a pattern.
  440. //
  441. // Notes:
  442. //   - Make sure to allocate enough nodes (2 * number_of_original_nodes).
  443. // -----------------------------------------------------------------
  444.  
  445. // 3.3) MAXIMUM WEIGHT CLOSURE (Min Cut Application)
  446. // -----------------------------------------------------------------
  447. // What it solves:
  448. //   You have a set of projects (nodes). Each project gives a certain profit
  449. //   (can be positive or negative). There are dependencies: to take project A,
  450. //   you must take project B. Find the maximum total profit you can achieve.
  451. //
  452. // Idea (simplified):
  453. //   - Positive profit projects are connected from Source with capacity = profit.
  454. //   - Negative profit projects are connected to Sink with capacity = -profit.
  455. //   - Dependencies (A depends on B) are added as edges (A -> B) with INF capacity.
  456. //   - Answer = (Sum of all positive profits) - maxFlow(Source, Sink).
  457. //
  458. // Input:
  459. //   - n: number of projects.
  460. //   - profits: vector of long long (size n), where profits[i] is the profit (can be negative).
  461. //   - deps: vector of pairs (a, b) meaning "if you take 'a', you must take 'b'".
  462. //
  463. // Output:
  464. //   - Returns the maximum achievable total profit.
  465. //
  466. // Time complexity:
  467. //   O(maxFlow) on a graph with n+2 nodes.
  468. //
  469. // Notes:
  470. //   - This is a classic problem in competitive programming.
  471. //   - If you don't understand the math, just follow the pattern.
  472. // -----------------------------------------------------------------
  473. long long maxWeightClosure(int n, const vector<long long>& profits, const vector<pair<int, int>>& deps) {
  474.     int S = n;
  475.     int T = n + 1;
  476.     Dinic dinic(n + 2);
  477.  
  478.     long long totalPositive = 0;
  479.     const long long INF = 4e18;
  480.  
  481.     for (int i = 0; i < n; i++) {
  482.         if (profits[i] > 0) {
  483.             dinic.addEdge(S, i, profits[i]);
  484.             totalPositive += profits[i];
  485.         } else if (profits[i] < 0) {
  486.             dinic.addEdge(i, T, -profits[i]); // capacity is positive
  487.         }
  488.     }
  489.  
  490.     for (auto [a, b] : deps) {
  491.         // If we take 'a', we must take 'b'.
  492.         // Edge a -> b with INF capacity means cutting this edge is too expensive,
  493.         // so the min cut won't separate a (source side) from b (sink side)
  494.         // unless b is cut off from the source.
  495.         dinic.addEdge(a, b, INF);
  496.     }
  497.  
  498.     long long minCut = dinic.maxFlow(S, T);
  499.     return totalPositive - minCut;
  500. }
  501.  
  502. // 3.4) FLOW WITH LOWER BOUNDS (Feasible Flow / Circulation)
  503. // -----------------------------------------------------------------
  504. // What it solves:
  505. //   Sometimes, edges don't just have a maximum capacity, but also a
  506. //   MINIMUM required flow (lower bound). We need to check if it's
  507. //   possible to send flow satisfying all lower and upper bounds.
  508. //   This function can handle both pure circulation (no source/sink)
  509. //   and standard s‑t flow with lower bounds.
  510. //
  511. // Input:
  512. //   - n: number of nodes.
  513. //   - edges: a vector of LowerBoundEdge (u, v, lower, upper).
  514. //            Means: edge from u to v must carry at least 'lower' and at most 'upper' flow.
  515. //   - s: (optional) source node for s‑t flow. Use -1 for circulation (default).
  516. //   - t: (optional) sink node for s‑t flow. Use -1 for circulation (default).
  517. //
  518. // Output:
  519. //   - Returns 'true' if a feasible flow exists, 'false' otherwise.
  520. //   - If 'true', the residual graph will contain the solution (flow values
  521. //     can be recovered if needed).
  522. //
  523. // Time complexity:
  524. //   O(maxFlow) on a graph with n+2 nodes and E edges.
  525. //
  526. // How it works (simplified):
  527. //   1. Create a new graph with a Super Source (SS) and Super Sink (TT).
  528. //   2. For each edge (u->v) with [L, U]:
  529. //        - Add edge (u -> v) with capacity (U - L). (The adjustable part).
  530. //        - Store the demand: demand[u] -= L; demand[v] += L.
  531. //   3. After processing all edges, for each node i:
  532. //        - If demand[i] > 0: add edge (SS -> i) with capacity demand[i].
  533. //        - If demand[i] < 0: add edge (i -> TT) with capacity -demand[i].
  534. //   4. If s and t are given (not -1), add an edge (t -> s) with INF capacity
  535. //      to convert the problem into a circulation.
  536. //   5. Run maxFlow(SS, TT). If the flow equals the sum of positive demands,
  537. //      then a feasible solution exists.
  538. //
  539. // Constraints:
  540. //   - 0 <= lower <= upper.
  541. //   - Nodes are 0-indexed.
  542. //   - If s and t are provided, they must be valid nodes and different.
  543. //
  544. // Notes:
  545. //   - This function does NOT return the actual flow values on edges,
  546. //     but the residual graph can be used to reconstruct them.
  547. //   - For pure circulation, call with s = -1, t = -1 (or omit the parameters).
  548. // -----------------------------------------------------------------
  549. struct LowerBoundEdge {
  550.     int u, v;
  551.     long long lower, upper;
  552. };
  553.  
  554. bool feasibleFlowWithLowerBounds(int n, const vector<LowerBoundEdge>& edges, int s = -1, int t = -1) {
  555.     int SS = n;
  556.     int TT = n + 1;
  557.     Dinic dinic(n + 2);
  558.  
  559.     vector<long long> demand(n, 0);
  560.     const long long INF = 4e18;
  561.  
  562.     for (const auto& e : edges) {
  563.         demand[e.u] -= e.lower;
  564.         demand[e.v] += e.lower;
  565.         dinic.addEdge(e.u, e.v, e.upper - e.lower);
  566.     }
  567.  
  568.     long long totalPositiveDemand = 0;
  569.     for (int i = 0; i < n; i++) {
  570.         if (demand[i] > 0) {
  571.             dinic.addEdge(SS, i, demand[i]);
  572.             totalPositiveDemand += demand[i];
  573.         } else if (demand[i] < 0) {
  574.             dinic.addEdge(i, TT, -demand[i]);
  575.         }
  576.     }
  577.  
  578.     // If we have a specific source and sink, add an infinite edge from sink to source
  579.     // to make it a circulation problem.
  580.     if (s != -1 && t != -1) {
  581.         dinic.addEdge(t, s, INF);
  582.     }
  583.  
  584.     long long maxflow = dinic.maxFlow(SS, TT);
  585.     return maxflow == totalPositiveDemand;
  586. }
  587.  
  588. // ===================================================================
  589. // 4) MISCELLANEOUS UTILITY WRAPPERS
  590. // ===================================================================
  591.  
  592. // 4.1) addUndirectedEdge
  593. // -----------------------------------------------------------------
  594. // What it solves:
  595. //   Adds an undirected edge between 'u' and 'v' with capacity 'cap'.
  596. //   This means flow can go from u to v up to cap, and from v to u up to cap,
  597. //   but the net flow (u->v minus v->u) cannot exceed cap in magnitude.
  598. //   (i.e., the total flow crossing the edge in either direction is bounded by cap).
  599. //
  600. // Input:
  601. //   u, v : the two nodes
  602. //   cap  : the maximum net capacity in either direction.
  603. //
  604. // How to use:
  605. //   dinic.addUndirectedEdge(u, v, cap);
  606. //
  607. // Notes:
  608. //   Internally, it adds two directed edges each with capacity 'cap'.
  609. //   This correctly models an undirected edge because positive flow in one
  610. //   direction cancels negative flow in the other direction in the residual graph.
  611. //   If you need independent capacities (u->v with cap1, v->u with cap2),
  612. //   just call addEdge(u, v, cap1) and addEdge(v, u, cap2) separately.
  613. // -----------------------------------------------------------------
  614. void addUndirectedEdge(Dinic& dinic, int u, int v, long long cap) {
  615.     dinic.addEdge(u, v, cap);
  616.     dinic.addEdge(v, u, cap);
  617. }
  618.  
  619. // 4.2) getMinCutEdges (Helper)
  620. // -----------------------------------------------------------------
  621. // What it solves:
  622. //   Given a Dinic graph after running maxFlow, and the reachable nodes,
  623. //   it returns a vector of the original edges that form the minimum cut.
  624. //
  625. // Input:
  626. //   - dinic: the Dinic object (must have run maxFlow() already).
  627. //   - reachable: the boolean vector from dinic.getReachableNodes(source).
  628. //   - originalEdges: a vector of the original directed edges that were added.
  629. //     (You need to store them when you call addEdge if you want to extract them).
  630. //
  631. // Output:
  632. //   - vector of pairs (u, v) representing the edges in the min cut.
  633. //
  634. // Note:
  635. //   Since we don't store the original edges in the class by default,
  636. //   this is just a demonstration pattern.
  637. // -----------------------------------------------------------------
  638. // vector<pair<int, int>> getMinCutEdges(Dinic& dinic, vector<bool>& reachable) {
  639. //     vector<pair<int, int>> cutEdges;
  640. //     for (int u = 0; u < dinic.n; u++) {
  641. //         if (!reachable[u]) continue;
  642. //         for (const auto& e : dinic.adj[u]) {
  643. //             // We need to know if 'e' is a forward edge.
  644. //             // Since we don't track that, it's easier to store the original edges list.
  645. //             // Just iterate over your stored original edges and check
  646. //             // reachable[edge.u] && !reachable[edge.v].
  647. //         }
  648. //     }
  649. //     return cutEdges;
  650. // }
  651.  
  652. // ===================================================================
  653. // main() with example usage (Black-box testing)
  654. // ===================================================================
  655.  
  656. int main() {
  657.     ios::sync_with_stdio(false);
  658.     cin.tie(nullptr);
  659.  
  660.     // Example 1: Simple Max Flow
  661.     // Nodes: 0, 1, 2, 3. Source = 0, Sink = 3.
  662.     // Edges: 0->1 (10), 0->2 (10), 1->3 (10), 2->3 (10), 1->2 (5).
  663.     cout << "=== Example 1: Simple Max Flow ===\n";
  664.     {
  665.         Dinic dinic(4);
  666.         dinic.addEdge(0, 1, 10);
  667.         dinic.addEdge(0, 2, 10);
  668.         dinic.addEdge(1, 3, 10);
  669.         dinic.addEdge(2, 3, 10);
  670.         dinic.addEdge(1, 2, 5);
  671.  
  672.         long long flow = dinic.maxFlow(0, 3);
  673.         cout << "Max Flow: " << flow << "\n"; // Expected: 20 (Path 0-1-3 and 0-2-3)
  674.     }
  675.  
  676.     // Example 2: Bipartite Matching
  677.     // Left: 0, 1. Right: 0, 1.
  678.     // Edges: (0,0), (0,1), (1,0).
  679.     cout << "\n=== Example 2: Bipartite Matching ===\n";
  680.     {
  681.         vector<pair<int, int>> edges = {{0, 0}, {0, 1}, {1, 0}};
  682.         int matches = maxBipartiteMatching(2, 2, edges);
  683.         cout << "Max Matches: " << matches << "\n"; // Expected: 2
  684.     }
  685.  
  686.     // Example 3: Max Weight Closure
  687.     // Projects: A(profit 10), B(profit -5), C(profit 6).
  688.     // Dependencies: A depends on B, C depends on B.
  689.     cout << "\n=== Example 3: Max Weight Closure ===\n";
  690.     {
  691.         vector<long long> profits = {10, -5, 6};
  692.         vector<pair<int, int>> deps = {{0, 1}, {2, 1}}; // 0->1, 2->1
  693.         long long maxProfit = maxWeightClosure(3, profits, deps);
  694.         cout << "Max Profit: " << maxProfit << "\n"; // Expected: 11 (Take A, B, C. Sum=11)
  695.     }
  696.  
  697.     // Example 4: Feasible Flow with Lower Bounds (Circulation)
  698.     cout << "\n=== Example 4: Feasible Flow with Lower Bounds (Circulation) ===\n";
  699.     {
  700.         // Nodes: 0, 1, 2.
  701.         // Edge 0->1: lower=5, upper=10
  702.         // Edge 1->2: lower=5, upper=10
  703.         // Edge 2->0: lower=5, upper=10 (to make a circulation)
  704.         vector<LowerBoundEdge> edges = {
  705.             {0, 1, 5, 10},
  706.             {1, 2, 5, 10},
  707.             {2, 0, 5, 10}
  708.         };
  709.         bool feasible = feasibleFlowWithLowerBounds(3, edges); // circulation
  710.         cout << "Feasible: " << (feasible ? "Yes" : "No") << "\n"; // Expected: Yes
  711.     }
  712.  
  713.     // Example 5: Feasible Flow with Lower Bounds (s-t flow)
  714.     cout << "\n=== Example 5: Feasible Flow with Lower Bounds (s-t) ===\n";
  715.     {
  716.         // Nodes: 0,1,2. Source=0, Sink=2.
  717.         // Edge 0->1: lower=2, upper=5
  718.         // Edge 1->2: lower=3, upper=6
  719.         // Also need an edge 2->0 with lower=0, upper=INF to make circulation? Actually for s-t,
  720.         // we add the infinite edge automatically when we pass s and t.
  721.         vector<LowerBoundEdge> edges = {
  722.             {0, 1, 2, 5},
  723.             {1, 2, 3, 6}
  724.         };
  725.         bool feasible = feasibleFlowWithLowerBounds(3, edges, 0, 2);
  726.         cout << "Feasible: " << (feasible ? "Yes" : "No") << "\n"; // Expected: Yes (can send 3-5 flow)
  727.     }
  728.  
  729.     return 0;
  730. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
=== Example 1: Simple Max Flow ===
Max Flow: 20

=== Example 2: Bipartite Matching ===
Max Matches: 2

=== Example 3: Max Weight Closure ===
Max Profit: 11

=== Example 4: Feasible Flow with Lower Bounds (Circulation) ===
Feasible: Yes

=== Example 5: Feasible Flow with Lower Bounds (s-t) ===
Feasible: Yes
https://ideone.com/7VqaZ2
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!