IanisBelu

E. Build String

Oct 23rd, 2023
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.35 KB | Source Code | 0 0
  1. #pragma GCC optimize("Ofast,unroll-loops")
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <fstream>
  5. #include <queue>
  6. #include <cstring>
  7.  
  8. #define sz(a) ((int)(a).size())
  9. #define all(a) (a).begin(), (a).end()
  10.  
  11. #define fi first
  12. #define se second
  13.  
  14. #define lsb(x) (x & (-x))
  15.  
  16. using namespace std;
  17.  
  18. inline bool ckmin(int &a, int b) { if (a <= b) return false; else a = b; return true; }
  19. inline bool ckmax(int &a, int b) { if (a >= b) return false; else a = b; return true; }
  20.  
  21. #if 0
  22. #ifdef LOCAL
  23. ifstream fin("input.txt");
  24. #define fout cout
  25. #else
  26. #define FILE_NAME "fmcm"
  27. ifstream fin(FILE_NAME ".in");
  28. ofstream fout(FILE_NAME ".out");
  29. #define endl '\n'
  30. #endif
  31. #endif
  32.  
  33. typedef long long ll;
  34. typedef pair<int, int> pii;
  35.  
  36. const int NMAX = 205;
  37. const int INF = 2e9+5;
  38.  
  39. struct Edge {
  40.     int dest, cap, cost, other;
  41. };
  42.  
  43. int n, source, sink;
  44. vector<Edge> g[NMAX];
  45. int dist[NMAX], pi[NMAX], pi2[NMAX];
  46. int vis[NMAX];
  47. bool inq[NMAX];
  48. pii nxt[NMAX];
  49. string s;
  50. pair<string, int> a[NMAX];
  51. int fr[26], fr2[26];
  52.  
  53. void add_edge(int x, int y, int cap, int cost) {
  54.     if (!cap) return;
  55.     g[x].push_back({ y, cap, cost, sz(g[y]) });
  56.     g[y].push_back({ x, 0, -cost, sz(g[x]) - 1 });
  57. }
  58.  
  59. void read() {
  60.     cin >> s >> n;
  61.     for (int i = 1; i <= n; i++)
  62.         cin >> a[i].fi >> a[i].se;
  63. }
  64.  
  65. void bellman() {
  66.     queue<int> qe;
  67.  
  68.     for (int i = 1; i <= n; i++)
  69.         pi[i] = INF;
  70.  
  71.     qe.push(source);
  72.     pi[source] = 0;
  73.  
  74.     while (!qe.empty()) {
  75.         int u = qe.front();
  76.  
  77.         qe.pop();
  78.         inq[u] = false;
  79.  
  80.         for (auto &it : g[u]) {
  81.             if (it.cap && ckmin(pi[it.dest], pi[u] + it.cost)) {
  82.                 if (!inq[it.dest]) {
  83.                     qe.push(it.dest);
  84.                     inq[it.dest] = true;
  85.                 }
  86.             }
  87.         }
  88.     }
  89. }
  90.  
  91. void dijkstra() {
  92.     for (int i = 1; i <= n; i++) {
  93.         dist[i] = INF;
  94.         vis[i] = false;
  95.         pi2[i] = pi[i];
  96.     }
  97.  
  98.     priority_queue<pii> pq;
  99.  
  100.     pq.push({0, source});
  101.     dist[source] = pi[source] = 0;
  102.     nxt[source] = {0, 0};
  103.  
  104.     while (!pq.empty()) {
  105.         int u = pq.top().se;
  106.  
  107.         pq.pop();
  108.  
  109.         if (vis[u]) continue;
  110.         vis[u] = true;
  111.  
  112.         int i = -1;
  113.         for (auto &it : g[u]) {
  114.             i++;
  115.             if (it.cap && ckmin(dist[it.dest], dist[u] + it.cost + pi2[u] - pi2[it.dest])) {
  116.                 pi[it.dest] = pi[u] + it.cost;
  117.                 nxt[it.dest] = { u, i };
  118.                 pq.push({-dist[it.dest], it.dest});
  119.             }
  120.         }
  121.     }
  122. }
  123.  
  124. int solve() {
  125.     source = n + 27;
  126.     sink = n + 28;
  127.    
  128.     for (int i = 1; i <= n; i++) {
  129.         add_edge(source, i, a[i].se, 0);
  130.         memset(fr, 0, sizeof(fr));
  131.         for (auto &c : a[i].fi)
  132.             fr[c - (int)'a']++;
  133.  
  134.         for (int j = 0; j < 26; j++)
  135.             add_edge(i, n + j + 1, fr[j], i);
  136.     }
  137.  
  138.     for (auto &c : s) fr2[c - (int)'a']++;
  139.  
  140.     for (int i = 0; i < 26; i++)
  141.         add_edge(n + i + 1, sink, fr2[i], 0);
  142.  
  143.     n += 28;
  144.  
  145.     int max_flow = 0, min_cost = 0;
  146.     bellman();
  147.     while (dijkstra(), dist[sink] != INF) {
  148.         int flow = INF, cost = 0;
  149.         for (int u = sink; u != source; u = nxt[u].fi) {
  150.             Edge &e = g[nxt[u].fi][nxt[u].se];
  151.             cost += e.cost;
  152.             ckmin(flow, e.cap);
  153.         }
  154.         for (int u = sink; u != source; u = nxt[u].fi) {
  155.             Edge &e = g[nxt[u].fi][nxt[u].se];
  156.             e.cap -= flow;
  157.             g[u][e.other].cap += flow;
  158.         }
  159.         max_flow += flow;
  160.         min_cost += flow * cost;
  161.     }
  162.     return max_flow == sz(s) ? min_cost : -1;
  163. }
  164.  
  165. signed main() {
  166. #ifdef LOCAL
  167.     freopen("input.txt", "r", stdin);
  168. #else
  169.     ios_base::sync_with_stdio(false);
  170.     cin.tie(0);
  171.     cout.tie(0);
  172. #endif
  173.     read();
  174.     cout << solve() << endl;
  175.     return 0;
  176. }
  177.  
Advertisement
Add Comment
Please, Sign In to add comment