Advertisement
Guest User

Untitled

a guest
Mar 28th, 2022
508
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int const inf = 1000000000;
  9.  
  10. class MaxFlow{
  11. private:
  12.   struct Edge{
  13.     int to;
  14.     int rev;
  15.     int flow;
  16.     int cap;
  17.   };
  18.   int n;
  19.   std::vector<std::vector<Edge>> g;
  20.   std::vector<int> level, rem;
  21.   int source;
  22.   int sink;
  23. public:
  24.   MaxFlow(int n_) {
  25.     n = n_;
  26.     source = 0;
  27.     sink = n - 1;
  28.  
  29.     g.resize(n);
  30.     level.resize(n);
  31.     rem.resize(n);
  32.   }
  33.   void addEdge(int x, int y, int cap) {
  34.     g[x].push_back({y, (int)g[y].size(), 0, cap});
  35.     g[y].push_back({x, (int)g[x].size() - 1, 0, 0});
  36.   }
  37.   void setSourceSink(int _source, int _sink) {
  38.     source = _source;
  39.     sink = _sink;
  40.   }
  41.   bool BFS() {
  42.     for(int i = 0; i < n; i++)
  43.       level[i] = -1;
  44.     std::queue<int> q;
  45.     level[source] = 0;
  46.     q.push(source);
  47.     while(0 < q.size()) {
  48.       int node = q.front();
  49.       q.pop();
  50.       for(int h = 0; h < g[node].size(); h++) {
  51.         Edge e = g[node][h];
  52.         if(e.flow < e.cap && level[e.to] == -1) {
  53.           level[e.to] = level[node] + 1;
  54.           q.push(e.to);
  55.         }
  56.       }
  57.     }
  58.     return 0 <= level[sink];
  59.   }
  60.   int DFS(int node, int delta) {
  61.     if(node == sink)
  62.       return delta;
  63.     else {
  64.       for(int &h = rem[node]; h < g[node].size(); h++) {
  65.         Edge &e = g[node][h];
  66.         if(e.flow < e.cap && level[node] + 1 == level[e.to]) {
  67.           int deltaflow = DFS(e.to, std::min(delta, e.cap - e.flow));
  68.           if(0 < deltaflow) {
  69.             e.flow += deltaflow;
  70.             g[e.to][e.rev].flow -= deltaflow;
  71.             return deltaflow;
  72.           }
  73.         }
  74.       }
  75.       return 0;
  76.     }
  77.   }
  78.   int64_t maxflow() {
  79.     int64_t result = 0, delta = 0;
  80.     while(BFS()) {
  81.       for(int i = 0; i < n; i++)
  82.         rem[i] = 0;
  83.       delta = 0;
  84.       do {
  85.         result += delta;
  86.         delta = DFS(source, inf);
  87.       } while(0 < delta);
  88.     }
  89.     return result;
  90.   }
  91. };
  92.  
  93. int main()
  94. {
  95.   int n;
  96.   std::cin >> n;
  97.   MaxFlow graph(3 + n);
  98.   graph.setSourceSink(1, 2 + n);
  99.   int64_t result = 0 ;
  100.   for(int i = 1; i <= n; i++) {
  101.     int val, cost;
  102.     std::cin >> val >> cost;
  103.     val -= cost;
  104.     if(0 <= val) {
  105.       graph.addEdge(1, 1 + i, val);
  106.       result += val;
  107.     }else
  108.       graph.addEdge(1 + i, 2 + n, -val);
  109.     int dep;
  110.     std::cin >> dep;
  111.     for(int j = 1; j <= dep; j++) {
  112.       int node;
  113.       std::cin >> node;
  114.       graph.addEdge(1 + node, 1 + i, inf);
  115.     }
  116.   }
  117.   std::cout << result - graph.maxflow() << '\n';
  118.   return 0;
  119. }
  120.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement