Shipping Center [パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195） D]

https://atcoder.jp/contests/abc195/tasks/abc195_d

前提知識

• 最小費用流

解説

https://atcoder.jp/contests/abc195/submissions/20908448 この解法は非想定解です。
想定解は貪欲法であるが、貪欲法を確信的に行うのはやや難しい。
自分は、アルゴリズムの力で何とかなる場合はそちらを採用している。

まずは1クエリ単体で解法を考えてみよう。
パッと見た感じ、マッチング問題のように見える。
マッチング問題といえばフローであるが、最小費用流を使えば問題は解けそうだ。
最小費用流について細かな説明はしないので、他で学習してきてほしい。
今回の問題は各クエリ毎に独立して、最小費用流を使って解ける。

フロー構成

最小費用流だが、最大値を求める問題であるので、
「費用はMAX-コストとして、MAX*最大流量-最小コストが答え」
とやるテクを使う。

フローは以下の通り。表記は(最大流量,コスト)である。

始点→荷物i (1,0)
使える箱jについて、荷物i→箱j (箱jに荷物iが入れられる場合は1でそうでないなら0, MAX-V[i])
箱j→終点 (1,0)

後は、フローを流せばいい。

int N, M, Q, W[50], V[50], X[50];
int L, R;
//---------------------------------------------------------------------------------------------------
int solve() {
    atcoder::mcf_graph<int, ll> mcf(N + M + 2);

    int st = N + M;
    int gl = st + 1;
    int MAX = 1010101;

    rep(i, 0, N) mcf.add_edge(st, i, 1, 0);
    rep(i, 0, N) rep(j, 0, M) {
        if (L - 1 <= j && j <= R - 1) continue;
        mcf.add_edge(i, N + j, (W[i] <= X[j]), MAX - V[i]);
    }
    rep(j, 0, M) mcf.add_edge(N + j, gl, 1, 0);

    int flow;
    ll cost;
    tie(flow, cost) = mcf.flow(st, gl);
    return 1LL * MAX * flow - cost;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> Q;
    rep(i, 0, N) cin >> W[i] >> V[i];
    rep(i, 0, M) cin >> X[i];
    rep(_, 0, Q) {
        cin >> L >> R;
        cout << solve() << endl;
    }
}