[toph.co] Budget Travel

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Budget Travel
Source            : toph.co
Category          : Graph Theory
Algorithm         : Min Cost Max Flow
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 1e3 + 5;  


//Works for negative costs, but does not work for negative cycles  
//Complexity: O(min(E^2 *V log V, E logV * flow))  
  
struct edge  
{  
    int to, flow, cap, cost, 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, curflow, prevedge, prevnode, q, 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};  
    }  
};  
  
int desCost[maxn];  
  
int main()  
{  
      //freopen("in.txt", "r", stdin);  
  
      int N, D;  
      scanf("%d %d", &D, &N);  
      MinCostMaxFlow mcmf(N+D+2);  
      for (int i = 1; i <= D; i++) scanf("%d", &desCost[i+N]);  
      for (int u = 1; u <= N; u++)  
      {  
          int prefers;  
          scanf("%d", &prefers);  
          for (int i = 1; i <= prefers; i++)  
          {  
                int v;  
                scanf("%d", &v);  
                v += N;  
                mcmf.addEdge(u, v, 1, desCost[v]);  
                mcmf.addEdge(v, u, 1, desCost[v]);  
          }  
      }  
      if (D < N)  
      {  
            puts("-1");  
            exit(0);  
      }  
      int S = 0;  
      int T = N + D + 1;  
      for (int v = 1; v <= N; v++)  
      {  
            mcmf.addEdge(S, v, 1, 0);  
            mcmf.addEdge(v, S, 1, 0);  
      }  
      for (int u = N+1; u <= N+D; u++)  
      {  
            mcmf.addEdge(u, T, 1, 0);  
            mcmf.addEdge(T, u, 1, 0);  
      }  
      pair <int, int> res = mcmf.minCostFlow(S, T, N);  
      if (res.first != N) res.second = -1;  
      printf("%d\n", res.second);  
}