fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. const int inf = 1e18;
  8. const int N = 1e3 + 5;
  9. int n, m;
  10. int D[N];
  11. struct Dinic {
  12.     struct Edge {
  13.         int v, rev;
  14.         long long cap, flow;
  15.     };
  16.     long long INF = 4e18;
  17.     int N;
  18.     vector<vector<Edge>> G;
  19.     vector<int> level, curEdge;
  20.     Dinic (int n = 0) {
  21.         init(n);
  22.     };
  23.     void init(int n) {
  24.         N = n;
  25.         G.assign(n, {});
  26.     }
  27.     void addEdge(int u, int v, long long cap) {
  28.         Edge a{v, (int)G[v].size(), cap, 0};
  29.         Edge b{u, (int)G[u].size(), 0, 0};
  30.         G[u].push_back(a);
  31.         G[v].push_back(b);
  32.     }
  33.  
  34.     bool bfs(int s, int t) {
  35.         level.assign(N, -1);
  36.         level[s] = 0;
  37.         queue<int> Q;
  38.         Q.push(s);
  39.  
  40.         while(!Q.empty() && level[t] == -1) {
  41.             int u = Q.front(); Q.pop();
  42.             for (Edge &e: G[u]) {
  43.                 if (e.cap > e.flow && level[e.v] == -1) {
  44.                     level[e.v] = level[u] + 1;
  45.                     Q.push(e.v);
  46.                 }
  47.             }
  48.         }
  49.         return level[t] != -1;
  50.     }
  51.     long long dfs(int u, int t, long long f) {
  52.         if (!f || u == t) return f;
  53.         for (int &i = curEdge[u]; i < (int)G[u].size(); i++) {
  54.             Edge &e = G[u][i];
  55.             if (e.cap > e.flow && level[e.v] == level[u] + 1) {
  56.                 long long val = dfs(e.v, t, min(f, e.cap - e.flow));
  57.                 if (val) {
  58.                     e.flow += val;
  59.                     G[e.v][e.rev].flow -= val;
  60.                     return val;
  61.                 }
  62.             }
  63.         }
  64.         return 0;
  65.     }
  66.     long long maxFlow(int s, int t) {
  67.         long long flow = 0;
  68.         while(bfs(s, t)) {
  69.             curEdge.assign(N, 0);
  70.             while(long long f = dfs(s, t, INF)) {
  71.                 flow += f;
  72.             }
  73.         }
  74.         return flow;
  75.     }
  76. };
  77. signed main() {
  78.     cin.tie(NULL)->sync_with_stdio(false);
  79.     if(ifstream("Input.inp")) {
  80.         freopen("Input.inp", "r", stdin);
  81.         freopen("Output.out", "w", stdout);
  82.     }
  83.     cin >> n >> m;
  84.     Dinic dinic(n + 5);
  85.     int s = n + 1, t = n + 2;
  86.     for (int i = 1; i <= m; i++) {
  87.         int u, v; cin >> u >> v;
  88.         D[u]--;
  89.         D[v]++;
  90.         dinic.addEdge(u, v, inf);
  91.     }
  92.  
  93.     int sum = 0;
  94.     for (int i = 1; i <= n; ++i) {
  95.         if (D[i] > 0) {
  96.             dinic.addEdge(s, i, D[i]);
  97.             sum += D[i];
  98.         } else if (D[i] < 0) dinic.addEdge(i, t, -D[i]);
  99.     }
  100.  
  101.     int maxflow = dinic.maxFlow(s, t);
  102.     cout << sum - maxflow << endl;
  103.     return 0;
  104. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/RrfLEM
language:
C++14 (gcc 8.3)
created:
11 hours 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!