GCJ 2017 Round 2 Roller Coaster Scheduling

#include <algorithm>
#include <climits>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#ifdef TEST
#define CERR(str)        \
  do {                   \
    cerr << str << endl; \
  } while (false)
#else
#define CERR(str) \
  do {            \
  } while (false)
#define endl '\n'
#endif

#define eps 1e-9

#define ZERO(a) memset(a, 0, sizeof(a))
#define INTINF(a) memset(a, 0x3f, sizeof(a))
#define INTINFVAR(a) memset(&a, 0x3f, sizeof(a))
#define DOUBLEINF(a) memset(a, 0x7f, sizeof(a))
#define DOUBLEINFVAR(a) memset(&a, 0x7f, sizeof(a))
#define INTNEG(a) memset(a, -1, sizeof(a))
#define INTNEGVAR(a) memset(&a, -1, sizeof(a))
#define DOUBLENEG(a) memset(a, 0xfe, sizeof(a))
#define DOUBLENEGVAR(a) memset(&a, 0xfe, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define COPY(src, dest) memcpy(dest, src, sizeof(src))
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define FORb(i, a, b, extraCondition) \
  for (int i = a; i < (b) && (extraCondition); i++)
#define REP(n) FOR(randomVariableName, 0, n)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define FORdb(i, a, b, extraCondition) \
  for (int i = (b)-1; i >= (a) && (extraCondition); i--)
#define MIN(a, b) a = min((a), b)
#define MAX(a, b) a = max((a), (b))

typedef long long int ll;
typedef pair<int, int> pp;

int T;

// Taken from
// https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/MinCostMaxFlow.h
// I have no idea how it works, this is not an algorithm I put in any effort to
// understanding yet so just took a good implementation
/**
 * Author: Stanford
 * Date: Unknown
 * Source: Stanford Notebook
 * Description: Min-cost max-flow. cap[i][j] != cap[j][i] is allowed; double
 * edges are not. If costs can be negative, call setpi before maxflow, but note
 * that negative cost cycles are not supported. To obtain the actual flow, look
 * at positive values only. Status: Tested on kattis mincostmaxflow Time:
 * Approximately O(E^2)
 */
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#include <cassert>
#include <ext/pb_ds/priority_queue.hpp>

const ll INF = numeric_limits<ll>::max() / 4;
typedef vector<ll> VL;

struct MCMF {
  int N;
  vector<vi> ed, red;
  vector<VL> cap, flow, cost;
  vi seen;
  VL dist, pi;
  vector<pii> par;

  MCMF(int N)
      : N(N),
        ed(N),
        red(N),
        cap(N, VL(N)),
        flow(cap),
        cost(cap),
        seen(N),
        dist(N),
        pi(N),
        par(N) {}

  void addEdge(int from, int to, ll cap, ll cost) {
    this->cap[from][to] = cap;
    this->cost[from][to] = cost;
    ed[from].push_back(to);
    red[to].push_back(from);
  }

  void path(int s) {
    fill(all(seen), 0);
    fill(all(dist), INF);
    dist[s] = 0;
    ll di;

    __gnu_pbds::priority_queue<pair<ll, int>> q;
    vector<decltype(q)::point_iterator> its(N);
    q.push({0, s});

    auto relax = [&](int i, ll cap, ll cost, int dir) {
      ll val = di - pi[i] + cost;
      if (cap && val < dist[i]) {
        dist[i] = val;
        par[i] = {s, dir};
        if (its[i] == q.end())
          its[i] = q.push({-dist[i], i});
        else
          q.modify(its[i], {-dist[i], i});
      }
    };

    while (!q.empty()) {
      s = q.top().second;
      q.pop();
      seen[s] = 1;
      di = dist[s] + pi[s];
      trav(i, ed[s]) if (!seen[i])
          relax(i, cap[s][i] - flow[s][i], cost[s][i], 1);
      trav(i, red[s]) if (!seen[i]) relax(i, flow[i][s], -cost[i][s], 0);
    }
    rep(i, 0, N) pi[i] = min(pi[i] + dist[i], INF);
  }

  pair<ll, ll> maxflow(int s, int t) {
    ll totflow = 0, totcost = 0;
    while (path(s), seen[t]) {
      ll fl = INF;
      for (int p, r, x = t; tie(p, r) = par[x], x != s; x = p)
        fl = min(fl, r ? cap[p][x] - flow[p][x] : flow[x][p]);
      totflow += fl;
      for (int p, r, x = t; tie(p, r) = par[x], x != s; x = p)
        if (r)
          flow[p][x] += fl;
        else
          flow[x][p] -= fl;
    }
    rep(i, 0, N) rep(j, 0, N) totcost += cost[i][j] * flow[i][j];
    return {totflow, totcost};
  }

  // If some costs can be negative, call this before maxflow:
  void setpi(int s) {  // (otherwise, leave this out)
    fill(all(pi), INF);
    pi[s] = 0;
    int it = N, ch = 1;
    ll v;
    while (ch-- && it--)
      rep(i, 0, N) if (pi[i] != INF) trav(
          to, ed[i]) if (cap[i][to]) if ((v = pi[i] + cost[i][to]) < pi[to])
          pi[to] = v,
          ch = 1;
    assert(it >= 0);  // negative cost cycle
  }
};

int main() {
#ifndef TEST
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cerr.setstate(ios_base::failbit);
#endif
  cin >> T;
  FOR(CASE, 1, T + 1) {
    cout << "Case #" << CASE << ": ";
    int N, C, M;
    cin >> N >> C >> M;
    vector<int> ticketsA(N, 0), ticketsB(N, 0);
    REP(M) {
      int P, B;
      cin >> P >> B;
      P--;
      if (B == 1)
        ticketsA[P]++;
      else
        ticketsB[P]++;
    }
    MCMF g(2 * N + 2);
    const int source = 2 * N, sink = 2 * N + 1;
    bool bIteratedOver = false;
    FOR(i, 0, N) {
      if (ticketsA[i]) {
        g.addEdge(source, i, ticketsA[i], 0);
        FOR(j, 0, N) {
          if (!bIteratedOver && ticketsB[j]) {
            g.addEdge(j + N, sink, ticketsB[j], 0);
          }
          if (i == 0 && j == 0) continue;
          if (ticketsB[j]) {
            g.addEdge(i, j + N, M + 100, i == j);
          }
        }
        bIteratedOver |= true;
      }
    }

    auto ret = g.maxflow(source, sink);
    ll flow = ret.first;
    ll cost = ret.second;
    ll rides = M - flow;
    ll promotions = cost;

    // // Formula solution
    // int numTicketsA = 0, numTicketsB = 0;
    // FOR(i, 0, N) {
    //   numTicketsA += ticketsA[i];
    //   numTicketsB += ticketsB[i];
    // }
    // int ridesSol = max(numTicketsA, numTicketsB);
    // MAX(ridesSol, ticketsA[0] + ticketsB[0]);
    // int promotionsSol = 0;
    // FOR(i, 0, N) { MAX(promotionsSol, ticketsA[i] + ticketsB[i]); }
    // promotionsSol -= min(ridesSol, promotionsSol);

    // Max flow solution
    cout << rides << ' ' << promotions;

    // // Formula solution
    // cout << ridesSol << ' ' << promotionsSol << endl;

    cout << endl;
  }
}