Advertisement
Guest User

Untitled

a guest
Dec 8th, 2016
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.68 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
  5. #define REP(i, n) FOR(i, 0, n)
  6.  
  7. typedef long long llint;
  8.  
  9. // Min-cost max-flow (uses DFS)
  10. //
  11. // Given a directed weighted graph, source, and sink, computes the minimum cost
  12. // of the maximum flow from source to sink.
  13. // This version uses DFS to find shortest paths and gives good performance on
  14. // very "shallow" graphs: graphs which have very short paths between source
  15. // and sink (e.g. at most 10 edges).
  16. // In such cases this algorithm can be orders of magnitude faster than the
  17. // Dijkstra version.
  18. //
  19. // To use, call init(n), then add edges using edge(x, y, c, w), and finally
  20. // call run(src, sink).
  21. //
  22. // Functions:
  23. // - init(n) initializes the algorithm with the given number of nodes
  24. // - edge(x, y, c, w) adds an edge x->y with capacity c and weight w
  25. // - run(src, sink) runs the algorithm and returns {total_cost, total_flow}
  26. //
  27. // Time complexity: O(V * E^3)
  28. //
  29. // Constants to configure:
  30. // - MAXV is the maximum number of vertices
  31. // - MAXE is the maximum number of edges (i.e. twice the calls to function edge)
  32. // - oo is the "infinity" value
  33.  
  34. namespace Mcmf {
  35.   const int MAXV = 1000100;
  36.   const int MAXE = 1000100;
  37.   const llint oo = 1e18;
  38.  
  39.   int V, E;
  40.   int last[MAXV], curr[MAXV], bio[MAXV]; llint pi[MAXV];
  41.   int next[MAXE], adj[MAXE]; llint cap[MAXE], cost[MAXE];
  42.  
  43.   void init(int n) {
  44.     V = n;
  45.     E = 0;
  46.     REP(i, V) last[i] = -1;
  47.     REP(i, V) pi[i] = 0;
  48.   }
  49.  
  50.   void edge(int x, int y, llint c, llint w) {
  51.     adj[E] = y; cap[E] = c; cost[E] = +w; next[E] = last[x]; last[x] = E++;
  52.     adj[E] = x; cap[E] = 0; cost[E] = -w; next[E] = last[y]; last[y] = E++;
  53.   }
  54.  
  55.   llint push(int x, int sink, llint flow) {
  56.     if (x == sink) return flow;
  57.     if (bio[x]) return 0;
  58.     bio[x] = true;
  59.  
  60.     for (int &e = curr[x]; e != -1; e = next[e]) {
  61.       int y = adj[e];
  62.  
  63.       if (cap[e] && pi[x] == pi[y] + cost[e])
  64.         if (llint f = push(y, sink, min(flow, cap[e])))
  65.           return cap[e] -= f, cap[e^1] += f, f;
  66.     }
  67.     return 0;
  68.   }
  69.  
  70.   pair<llint, llint> run(int src, int sink) {
  71.     llint total = 0;
  72.     llint flow = 0;
  73.     pi[src] = oo;
  74.  
  75.     for (;;) {
  76.       REP(i, V) bio[i] = false;
  77.       REP(i, V) curr[i] = last[i];
  78.  
  79.       while (llint f = push(src, sink, oo)) {
  80.         total += pi[src] * f;
  81.         flow += f;
  82.         REP(i, V) bio[i] = false;
  83.       }
  84.  
  85.       llint inc = oo;
  86.       REP(x, V) if (bio[x]) {
  87.         for (int e = last[x]; e != -1; e = next[e]) {
  88.           int y = adj[e];
  89.           if (cap[e] && !bio[y]) inc = min(inc, pi[y] + cost[e] - pi[x]);
  90.         }
  91.       }
  92.       if (inc == oo) break;
  93.  
  94.       REP(i, V) if (bio[i]) pi[i] += inc;
  95.     }
  96.     return {total, flow};
  97.   }
  98. }
  99.  
  100. int me(int x){return 1 + x;}
  101. int enemy(int x){return 101 + x;}
  102.  
  103. string type_enemy[101];
  104. int s_enemy[101], s_me[101];
  105.  
  106. int main()
  107. {
  108.   int n,m;
  109.     cin >> n >> m;
  110.     Mcmf::init(203);
  111.     for(int i = 1; i <= n; i++)
  112.         cin >> type_enemy[i] >> s_enemy[i];
  113.     for(int i = 1; i <= m; i++)
  114.         cin >> s_me[i];
  115.     int S = 1, T = 203;
  116.     Mcmf::edge(202, 203, 100, 0);
  117.     for(int i = 1; i <= m; i++)
  118.         Mcmf::edge(S, me(i), 1, 0);
  119.     for(int i = 1; i <= n; i++)
  120.         Mcmf::edge(enemy(i), T, 1, 0);
  121.     for(int i = 1; i <= m; i++)
  122.     {
  123.         for(int j = 1; j <= n; j++)
  124.             if(type_enemy[j] == "ATK")
  125.             {
  126.                 if(s_me[i] >= s_enemy[j])
  127.                     Mcmf::edge(me(i), enemy(j), 1, 10000 - (s_me[i] - s_enemy[j]));
  128.             }
  129.             else
  130.             {
  131.                 if(s_me[i] > s_enemy[j])
  132.                     Mcmf::edge(me(i), enemy(j), 1, 10000);
  133.             }
  134.         Mcmf::edge(me(i), 202, 1, 1000000 - s_me[i]);
  135.     }
  136.     auto ans = Mcmf::run(S,T);
  137.     cout << ans.first << endl;
  138.     cout << ans.second << endl;
  139.    
  140.     return 0;
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement