[Codeforces] E. Build String

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Build String
Source            : Codeforces
Category          : Graph Theory
Algorithm         : Min Cost Max Flow
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 100 + 5;  
static const int inf = 500 + 5;  
  
struct Edge  
{  
      int to;  
      int flow;  
      int cap;  
      int cost;  
      int rev;  
      Edge(int to = 0, int flow = 0, int cap = 0, int cost = 0, int rev = 0)  
            : to(to)  
            , flow(flow)  
            , cap(cap)  
            , cost(cost)  
            , rev(rev) {}  
};  
  
struct MinCostMaxFlow  
{  
      int nodes;  
      vector <int> prio;  
      vector <int> curflow;  
      vector <int> prevEdge;  
      vector <int> prevnode;  
      vector <int> q;  
      vector <int> pot;  
      vector <bool> inqueue;  
      vector< vector<Edge> > graph;  
  
      MinCostMaxFlow() {}  
      MinCostMaxFlow(int n)  
            : nodes(n)  
            , prio(n, 0)  
            , curflow(n, 0)  
            , prevEdge(n, 0)  
            , prevnode(n, 0)  
            , q(n, 0)  
            , pot(n, 0)  
            , inqueue(n, 0)  
            , graph(n) {}  
  
      void addEdge(int source, int to, int capacity, int cost)  
      {  
            Edge a = {to, 0, capacity, cost, (int)graph[to].size()};  
            Edge b = {source, 0, 0, -cost, (int)graph[source].size()};  
            graph[source].push_back(a);  
            graph[to].push_back(b);  
      }  
      void bellman_ford(int source, vector<int> &dist)  
      {  
            fill(dist.begin(), dist.end(), INT_MAX);  
            dist[source] = 0;  
            int qt=0;  
            q[qt++] = source;  
            for(int qh = 0;(qh-qt) % nodes != 0; qh++)  
            {  
                  int u = q[qh % nodes];  
                  inqueue[u] = false;  
                  for(auto &e : graph[u])  
                  {  
                        if(e.flow >= e.cap) continue;  
                        int v = e.to;  
                        int newDist = dist[u] + e.cost;  
                        if(dist[v] > newDist)  
                        {  
                              dist[v] = newDist;  
                              if(!inqueue[v])  
                              {  
                                    inqueue[v] = true;  
                                    q[qt++ % nodes] = v;  
                              }  
                        }  
                  }  
            }  
      }  
      pair<int, int> minCostFlow(int source, int dest, int maxflow)  
      {  
            bellman_ford(source, pot);  
            int flow = 0;  
            int flow_cost = 0;  
            while(flow < maxflow)  
            {  
                  priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;  
                  q.push({0, source});  
                  fill(prio.begin(), prio.end(), INT_MAX);  
                  prio[source] = 0;  
                  curflow[source] = INT_MAX;  
                  while(!q.empty())  
                  {  
                        int d = q.top().first;  
                        int u = q.top().second;  
                        q.pop();  
                        if(d != prio[u]) continue;  
                        for(int i = 0; i < graph[u].size(); i++)  
                        {  
                              Edge &e=graph[u][i];  
                              int v = e.to;  
                              if(e.flow >= e.cap) continue;  
                              int newPrio = prio[u] + e.cost + pot[u] - pot[v];  
                              if(prio[v] > newPrio)  
                              {  
                                    prio[v] = newPrio;  
                                    q.push({newPrio, v});  
                                    prevnode[v] = u;  
                                    prevEdge[v] = i;  
                                    curflow[v] = min(curflow[u], e.cap - e.flow);  
                              }  
                        }  
                  }  
                  if(prio[dest] == INT_MAX) break;  
                  for(int i = 0;i < nodes; i++) pot[i] += prio[i];  
                  int df = min(curflow[dest], maxflow - flow);  
                  flow += df;  
                  for(int v = dest; v!= source; v = prevnode[v])  
                  {  
                        Edge &e = graph[ prevnode[v] ][ prevEdge[v] ];  
                        e.flow += df;  
                        graph[v][e.rev].flow -= df;  
                        flow_cost += df * e.cost;  
                  }  
            }  
            return {flow, flow_cost};  
      }  
};  
  
string t;  
string arr[maxn];  
int cap[maxn];  
map <char, int> reqd;  
map <char, int> pos;  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> t;  
      int n;  
      cin >> n;  
      for (char ch : t) ++reqd[ch];  
      int N = t.size();  
      int nodes = n + reqd.size() + 2;  
      MinCostMaxFlow mcmf(nodes);  
      int ptr = 0;  
      int src = 0;  
      int sink = n + reqd.size() + 1;  
      for (auto it : reqd)  
      {  
            pos[it.first] = ++ptr;  
            mcmf.addEdge(n + ptr, sink, it.second, 0);  
      }  
      for (int i = 1; i <= n; i++)  
      {  
            cin >> arr[i] >> cap[i];  
            mcmf.addEdge(src, i, cap[i], 0);  
            map <char, int> cur;  
            for (char ch : arr[i]) ++cur[ch];  
            for (auto it : cur)  
            {  
                  if (reqd.find(it.first) == reqd.end()) continue;  
                  mcmf.addEdge(i, n + pos[it.first], it.second, i);  
            }  
      }  
      pair <int, int> res = mcmf.minCostFlow(src, sink, inf);  
      if (res.first != N) res.second = -1;  
      cout << res.second;  
}