Advertisement
FHVirus

Dinic Template - TIOJ 1236

Jun 8th, 2021
343
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.03 KB | None | 0 0
  1. // Knapsack DP is harder than FFT.
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
  5. #define ff first
  6. #define ss second
  7. #define pb emplace_back
  8. #define AI(x) begin(x),end(x)
  9. template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
  10. template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;}
  11. #ifdef OWO
  12. #define debug(args...) SDF(#args, args)
  13. #define OIU(args...) ostream& operator<<(ostream&O,args)
  14. #define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
  15. LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
  16. template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
  17. template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
  18. #else
  19. #pragma GCC optimize("Ofast")
  20. #define debug(...) ((void)0)
  21. #endif
  22.  
  23. /*      Dinic here      */
  24. // prob: TIOJ 1236
  25. // name: din
  26. // func: add flow
  27.  
  28. const int N = 225, INF = INT_MAX;
  29. struct DIN{
  30.     struct E{
  31.         int v, c, r;
  32.         E(int v, int c, int r):
  33.             v(v), c(c), r(r){}
  34.     };
  35.     vector<E> adj[N];
  36.     void add(int u, int v, int c){
  37.         adj[u].pb(v, c, (int) adj[v].size());
  38.         adj[v].pb(u, 0, (int) adj[u].size() - 1);
  39.     }
  40.     int n, s, t;
  41.     void init(int nn, int ss, int tt){
  42.         n = nn, s = ss, t = tt;
  43.         for(int i = 0; i <= n; ++i)
  44.             adj[i].clear();
  45.     }
  46.     int le[N], it[N];
  47.     int bfs(){
  48.         fill(le, le + N, -1); le[s] = 0;
  49.         queue<int> q; q.push(s);
  50.         while(!q.empty()){
  51.             int u = q.front(); q.pop();
  52.             for(auto [v, c, r]: adj[u]){
  53.                 if(c > 0 and le[v] == -1)
  54.                     le[v] = le[u] + 1, q.push(v);
  55.             }
  56.         }
  57.         return ~le[t];
  58.     }
  59.     int dfs(int u, int f){
  60.         if(u == t) return f;
  61.         for(int &i = it[u]; i < (int) adj[u].size(); ++i){
  62.             auto &[v, c, r] = adj[u][i];
  63.             if(c > 0 and le[v] == le[u] + 1){
  64.                 int d = dfs(v, min(c, f));
  65.                 if(d > 0){
  66.                     c -= d;
  67.                     adj[v][r].c += d;
  68.                     return d;
  69.                 }
  70.             }
  71.         }
  72.         return 0;
  73.     }
  74.     ll flow(){
  75.         ll ans = 0, d;
  76.         while(bfs()){
  77.             fill(it, it + N, 0);
  78.             while((d = dfs(s, INF)) > 0) ans += d;
  79.         }
  80.         return ans;
  81.     }
  82. } din;
  83.  
  84. /*      Dinic end       */
  85.  
  86. signed main(){
  87.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  88.     int n; cin >> n;
  89.     din.init(n * 2 + 1, 0, n * 2 + 1);
  90.     for(int i = 1; i <= n; ++i){
  91.         int v; cin >> v;
  92.         din.add(i, i + n, v);
  93.     }
  94.     int m; cin >> m;
  95.     vector<bool> in(n + 1, 0), ou(n + 1, 0);
  96.     for(int u, v, c; m; --m){
  97.         cin >> u >> v;
  98.         in[v] = 1; ou[u] = 1;
  99.         din.add(u + n, v, INF);
  100.     }
  101.     for(int i = 1; i <= n; ++i){
  102.         if(!in[i]) din.add(0, i, INF);
  103.         if(!ou[i]) din.add(i + n, n * 2 + 1, INF);
  104.     }
  105.     cout << din.flow();
  106.     return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement