fork download
copy 
  1. /**
  2.  *    author:  longvu
  3.  *    created: 09/13/24 18:15:17
  4. **/
  5. #include<bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. #define int long long
  10. #define sz(x) ((int)x.size())
  11. #define all(x) (x).begin(), (x).end()
  12. const int INF = 1e9;
  13. const int nax = (int)(100001);
  14. const int mod = 1e9 + 7;
  15.  
  16. template<class X, class Y>
  17. bool maximize(X& x, const Y y) {
  18.     if (y > x) {x = y; return true;}
  19.     return false;
  20. }
  21. template<class X, class Y>
  22. bool minimize(X& x, const Y y) {
  23.     if (y < x) {x = y; return true;}
  24.     return false;
  25. }
  26.  
  27. struct FlowEdge {
  28.     int v, u;
  29.     long long cap, flow = 0;
  30.     FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
  31. };
  32.  
  33. struct Dinic {
  34.     const long long flow_inf = 1e18;
  35.     vector<FlowEdge> edges;
  36.     vector<vector<int>> adj;
  37.     int n, m = 0;
  38.     int s, t;
  39.     vector<int> level, ptr;
  40.     queue<int> q;
  41.  
  42.     Dinic(int n, int s, int t) : n(n), s(s), t(t) {
  43.         adj.resize(n);
  44.         level.resize(n);
  45.         ptr.resize(n);
  46.     }
  47.  
  48.     void add_edge(int v, int u, long long cap) {
  49.         edges.emplace_back(v, u, cap);
  50.         edges.emplace_back(u, v, 0);
  51.         adj[v].push_back(m);
  52.         adj[u].push_back(m + 1);
  53.         m += 2;
  54.     }
  55.  
  56.     bool bfs() {
  57.         while (!q.empty()) {
  58.             int v = q.front();
  59.             q.pop();
  60.             for (int id : adj[v]) {
  61.                 if (edges[id].cap - edges[id].flow < 1)
  62.                     continue;
  63.                 if (level[edges[id].u] != -1)
  64.                     continue;
  65.                 level[edges[id].u] = level[v] + 1;
  66.                 q.push(edges[id].u);
  67.             }
  68.         }
  69.         return level[t] != -1;
  70.     }
  71.  
  72.     long long dfs(int v, long long pushed) {
  73.         if (pushed == 0)
  74.             return 0;
  75.         if (v == t)
  76.             return pushed;
  77.         for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
  78.             int id = adj[v][cid];
  79.             int u = edges[id].u;
  80.             if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1)
  81.                 continue;
  82.             long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
  83.             if (tr == 0)
  84.                 continue;
  85.             edges[id].flow += tr;
  86.             edges[id ^ 1].flow -= tr;
  87.             return tr;
  88.         }
  89.         return 0;
  90.     }
  91.  
  92.     long long run() {
  93.         long long f = 0;
  94.         while (true) {
  95.             fill(level.begin(), level.end(), -1);
  96.             level[s] = 0;
  97.             q.push(s);
  98.             if (!bfs())
  99.                 break;
  100.             fill(ptr.begin(), ptr.end(), 0);
  101.             while (long long pushed = dfs(s, flow_inf)) {
  102.                 f += pushed;
  103.             }
  104.         }
  105.         return f;
  106.     }
  107. };
  108.  
  109. #define Fi first
  110. #define Se second
  111.  
  112. int a[nax], b[nax];
  113. int32_t main() {
  114.     ios_base::sync_with_stdio(false);
  115.     cin.tie(0);
  116.     int n, m;
  117.     cin >> n >> m;
  118.     for (int i = 1; i <= n; ++i) {
  119.         cin >> a[i];
  120.     }
  121.     for (int i = 1; i <= m; ++i) {
  122.         cin >> b[i];
  123.     }
  124.     Dinic flow(n + m + 2, 0, n + m + 1);
  125.     int ans = 0;
  126.     for (int i = 1; i <= n; ++i) {
  127.         int l;
  128.         cin >> l;
  129.         ans += a[i];
  130.         flow.add_edge(0, i, a[i]);
  131.         for (int j = 1; j <= l; ++j) {
  132.             int x;
  133.             cin >> x;
  134.             flow.add_edge(i, n + x, INF);
  135.         }
  136.     }
  137.     for (int i = 1; i <= m; ++i) {
  138.         flow.add_edge(n + i, n + m + 1, b[i]);
  139.     }
  140.     ans -= flow.run();
  141.     cout << ans << '\n';
  142.     return 0;
  143. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/oigx6y
language:
C++14 (clang 8.0)
created:
6 days 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!