fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define all(x) begin(x), end(x)
  5.  
  6. template <int MAXV, class T = int> struct Dinic {
  7.     const static bool SCALING = true; // non-scaling = V^2E, Scaling=VElog(U) with higher constant
  8.     int lim = 1;
  9.     const T INF = numeric_limits<T>::max();
  10.     struct edge {
  11.         int to, rev;
  12.         T cap, flow;
  13.     };
  14.     int s = MAXV - 2, t = MAXV - 1;
  15.  
  16.     int level[MAXV], ptr[MAXV];
  17.     vector<edge> adj[MAXV];
  18.     void addEdge(int a, int b, T cap, bool isDirected = true) {
  19.         adj[a].push_back({b, adj[b].size(), cap, 0});
  20.         adj[b].push_back({a, adj[a].size() - 1, isDirected ? 0 : cap, 0});
  21.     }
  22.     bool bfs() {
  23.         queue<int> q({s});
  24.         fill(all(level), -1);
  25.         level[s] = 0;
  26.         while (!q.empty() && level[t] == -1) {
  27.             int v = q.front();
  28.             q.pop();
  29.             for (auto e : adj[v]) {
  30.                 if (level[e.to] == -1 && e.flow < e.cap && (!SCALING || e.cap - e.flow >= lim)) {
  31.                     q.push(e.to);
  32.                     level[e.to] = level[v] + 1;
  33.                 }
  34.             }
  35.         }
  36.         return level[t] != -1;
  37.     }
  38.     T dfs(int v, T flow) {
  39.         if (v == t || !flow)
  40.             return flow;
  41.         for (; ptr[v] < adj[v].size(); ptr[v]++) {
  42.             edge &e = adj[v][ptr[v]];
  43.             if (level[e.to] != level[v] + 1)
  44.                 continue;
  45.             if (T pushed = dfs(e.to, min(flow, e.cap - e.flow))) {
  46.                 e.flow += pushed;
  47.                 adj[e.to][e.rev].flow -= pushed;
  48.                 return pushed;
  49.             }
  50.         }
  51.         return 0;
  52.     }
  53.     long long calc() {
  54.         long long flow = 0;
  55.         for (lim = SCALING ? (1 << 30) : 1; lim > 0; lim >>= 1) {
  56.             while (bfs()) {
  57.                 fill(all(ptr), 0);
  58.                 while (T pushed = dfs(s, INF))
  59.                     flow += pushed;
  60.             }
  61.         }
  62.         return flow;
  63.     }
  64. };
  65.  
  66. Dinic<1001> dinic;
  67.  
  68. int main() { cin.tie(NULL);
  69.     int n = 1000;
  70.     for(int i=1; i<=n-2; i++){
  71.         dinic.addEdge(i, i+1, 100000000);
  72.         dinic.addEdge(i, n, 10000);
  73.         for(int j=i+3; j<=n-2; j++){
  74.             dinic.addEdge(i, j, 1);
  75.             dinic.addEdge(j, i, 1);
  76.         }
  77.     }
  78.     dinic.s = 1, dinic.t = n;
  79.     cout << dinic.calc() << '\n';
  80. }
Success #stdin #stdout 3.59s 35428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9980000
https://ideone.com/vh6Uxm
language:
C++14 (gcc 8.3)
created:
3 years 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!