Advertisement
Guest User

Dinitz reference implementation

a guest
Jul 17th, 2022
1,064
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <tuple>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. const ll INF = 1e18 + 1000;
  11.  
  12. // A reference implementation of Dinitz's algorithm
  13. // Note: this implementation has been created with educational
  14. // value in mind, not efficiency. Other implementations with
  15. // better constant factors exist; if you're looking for a black
  16. // box to use in a contest, you're better off looking elsewhere.
  17. // See more: https://codeforces.com/blog/entry/104960
  18.  
  19. // This struct represents the state of an edge, together with its
  20. // reverse edge that may appear in some G_f, during the execution
  21. // of the algorithm.
  22. struct Edge {
  23.   int from, to; // The edge is from->to in the original graph.
  24.   ll capac, flow;
  25.  
  26.   // Gets the endpoint other than u of the edge.
  27.   int oth (int u) {
  28.     return u ^ from ^ to; // xor trick
  29.   }
  30.  
  31.   // Gets the capacity of the edge u->oth(u) in G_f.
  32.   ll capacity (int u) {
  33.     if (u == from) {
  34.       return capac - flow;
  35.     } else {
  36.       return flow;
  37.     }
  38.   }
  39.  
  40.   // Returns whether the edge u->oth(u) exists in u.
  41.   bool exists (int u) {
  42.     return capacity(u) != 0;
  43.   }
  44.  
  45.   // Adds df flow to the edge in G if u == from,
  46.   // subtracts it otherwise.
  47.   void add_flow (int u, ll df) {
  48.     if (u == from) {
  49.       flow += df;
  50.     } else {
  51.       flow -= df;
  52.     }
  53.   }
  54. };
  55.  
  56. // At any given time, represents one particular G_f. We modify this class on the
  57. // fly when adding a flow.
  58. class MaxFlow {
  59.   // number of vertices
  60.   int n;
  61.   int source, sink;
  62.  
  63.   // adj[u] is the set of edges incident to u
  64.   vector<vector<Edge*>> adj;
  65.  
  66.   // we also keep a list of all edges, for easy retrieval of flow on edge
  67.   vector<Edge*> edges;
  68.  
  69.   // lvl[u] is the layer (or distance from s) at the current DAG.
  70.   // updated via dinitz_bfs
  71.   vector<int> lvl;
  72.  
  73.   void dinitz_bfs () {
  74.     // we use a value greater than n to denote "unexplored"
  75.     // or what is called "undefined" in the blog. no vertex actually
  76.     // has a distance greater than n.
  77.     lvl = vector<int> (n, n + 10);
  78.    
  79.     queue<int> Q;
  80.     Q.push(source);
  81.     lvl[source] = 0;
  82.  
  83.     while (!Q.empty()) {
  84.       int u = Q.front();
  85.       Q.pop();
  86.  
  87.       for (auto e : adj[u]) {
  88.         if (!e->exists(u)) {
  89.           continue;
  90.         }
  91.  
  92.         int v = e->oth(u);
  93.         if (lvl[v] > n) {
  94.           lvl[v] = lvl[u] + 1;
  95.           Q.push(v);
  96.         }
  97.  
  98.         // in the actual implementation, we don't explicitly add edges to the
  99.         // DAG. we simply say that an edge u->v is in the DAG if lvl[v] = lvl[u] + 1
  100.       }
  101.     }
  102.   }
  103.  
  104.   bool in_current_dag (int u, int v) {
  105.     return lvl[v] == lvl[u] + 1;
  106.   }
  107.  
  108.   // as in the blog, tries to push F flow from u
  109.   // returns how much flow could actually be pushed
  110.   // the third parameter is used to maintain what is
  111.   // called v.blocked in the blog; note that it is a
  112.   // reference.
  113.   ll dinitz_dfs (int u, ll F, vector<int> &blocked) {
  114.     if (u == sink) {
  115.       return F;
  116.     }
  117.  
  118.     ll flow_pushed = 0;
  119.     bool all_blocked = true;
  120.     for (auto e : adj[u]) {
  121.       int v = e->oth(u);
  122.       if (!in_current_dag(u, v)) {
  123.         continue;
  124.       }
  125.  
  126.       if (e->exists(u) && !blocked[v]) {
  127.         // note that here we use e->capacity(u) instead of
  128.         // the e.capacity - e.flow in the blog, as the Edge
  129.         // struct automatically modifies the capacities when
  130.         // we add flow.
  131.         ll dF = dinitz_dfs(v, min(F, e->capacity(u)), blocked);
  132.  
  133.         flow_pushed += dF;
  134.         F -= dF;
  135.         e->add_flow(u, dF);
  136.       }
  137.  
  138.       if (e->exists(u) && !blocked[v]) {
  139.         all_blocked = false;
  140.       }
  141.     }
  142.  
  143.     if (all_blocked) {
  144.       blocked[u] = true;
  145.     }
  146.  
  147.     return flow_pushed;
  148.   }
  149.  
  150.   void dinitz_dfs () {
  151.     vector<int> blocked (n, false);
  152.     dinitz_dfs(source, INF, blocked);
  153.   }
  154.  
  155. public:
  156.   MaxFlow (int _source, int _sink, const vector<tuple<int, int, ll>> &_edges)
  157.     : source(_source), sink(_sink) {
  158.     n = max(1 + source, 1 + sink);
  159.     for (auto e : _edges) {
  160.       n = max(n, max(1 + get<0>(e), 1 + get<1>(e)));
  161.     }
  162.  
  163.     adj = vector<vector<Edge*>> (n, vector<Edge*> (0));
  164.     for (auto e : _edges) {
  165.       auto ee = new Edge();
  166.       ee->from = get<0>(e);
  167.       ee->to = get<1>(e);
  168.       ee->flow = 0;
  169.       ee->capac = get<2>(e);
  170.  
  171.       edges.push_back(ee);
  172.       if (ee->from != ee->to) {
  173.         // don't add self-loops to the adjacency list; they don't do anything
  174.         // useful to the graph and may mess up the algorithm.
  175.         adj[ee->from].push_back(ee);
  176.         adj[ee->to].push_back(ee);
  177.       }
  178.     }
  179.   }
  180.  
  181.   ll calc_max_flow () {
  182.     while (true) {
  183.       dinitz_bfs();
  184.       if (lvl[sink] > n) {
  185.         // t is not reachable from s anymore.
  186.         break;
  187.       }
  188.       dinitz_dfs();
  189.     }
  190.  
  191.     ll ans = 0;
  192.     for (auto e : adj[source]) {
  193.       if (e->from == source) {
  194.         ans += e->flow;
  195.       } else {
  196.         ans -= e->flow;
  197.       }
  198.     }
  199.  
  200.     return ans;
  201.   }
  202.  
  203.   ll flow_on_edge (int idx) {
  204.     return edges[idx]->flow;
  205.   }
  206. };
  207.  
  208. // convenience class for building the graph without awkward make_tuples
  209. class GraphBuilder {
  210.   int source, sink;
  211.   vector<tuple<int, int, ll>> edges;
  212.  
  213. public:
  214.   GraphBuilder (int _source, int _sink) : source(_source), sink(_sink), edges(0) {}
  215.  
  216.   void add_edge (int u, int v, ll capacity) {
  217.     edges.push_back(make_tuple(u, v, capacity));
  218.   }
  219.  
  220.   MaxFlow build () {
  221.     return MaxFlow(source, sink, edges);
  222.   }
  223. };
  224.  
  225. int main () {
  226.   ios::sync_with_stdio(false);
  227.   cin.tie(0);
  228.  
  229.   int n, m;
  230.   cin >> n >> m;
  231.  
  232.   GraphBuilder gb (1, n);
  233.   for (int i = 0; i < m; i++) {
  234.     int u, v;
  235.     ll capac;
  236.     cin >> u >> v >> capac;
  237.  
  238.     gb.add_edge(u, v, capac);
  239.     // in case of undirected edges:
  240.     // gb.add_edge(v, u, capac);
  241.   }
  242.  
  243.   auto mf = gb.build();
  244.   ll ans = mf.calc_max_flow();
  245.   cout << ans << '\n';
  246. }
  247.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement