はまやんはまやんはまやん

hamayanhamayan's blog

Air E869120 [yukicoder No.654]

https://yukicoder.me/problems/no/654

前提知識

解法

https://yukicoder.me/submissions/239081

最大流問題に帰着できる。
公式解説の図の通りに辺を張る。
 
少し細かく説明する。
次の飛行までにdだけ間を開ける必要があるが、これをQ[i]に到着ではなくQ[i]+dに到着すると考えることで、間を開けることを考えなくする。
全ての街について全ての時間を用意すると頂点数が膨大になるので、必要な部分だけ考える。
M個の移動の端点だけの頂点を用意すればいいので、各町について使われている時刻をまとめて、座圧して使う。
同じ街の隣り合う時刻に∞コストの辺を張り、全ての移動の辺を張り、街0の最初の時間から街N-1の最後の時間へ最大流を流せば答え。

int N, M, d, U[1010], V[1010], P[1010], Q[1010], W[1010];
vector<int> dic[1010];
int sz[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> d;
    rep(i, 0, M) {
        cin >> U[i] >> V[i] >> P[i] >> Q[i] >> W[i];
        U[i]--; V[i]--;
        Q[i] += d;
    }
    rep(i, 0, M) {
        dic[U[i]].push_back(P[i]);
        dic[V[i]].push_back(Q[i]);
    }
    rep(i, 0, N) {
        sort(all(dic[i]));
        dic[i].erase(unique(all(dic[i])), dic[i].end());
    }

    sz[0] = dic[0].size();
    rep(i, 1, N) sz[i] = sz[i - 1] + dic[i].size();

    MaxFlow<ll> mf(sz[N-1]);
    rep(i, 0, N) {
        int st = 0;
        if (i) st += sz[i - 1];
        int n = dic[i].size();
        rep(j, 0, n - 1) mf.add_edge(st + j, st + j + 1, infl);
    }
    rep(i, 0, M) {
        int a = lower_bound(all(dic[U[i]]), P[i]) - dic[U[i]].begin();
        if (U[i]) a += sz[U[i] - 1];
        int b = lower_bound(all(dic[V[i]]), Q[i]) - dic[V[i]].begin();
        if (V[i]) b += sz[V[i] - 1];
        mf.add_edge(a, b, W[i]);
    }
    
    ll ans = mf.maxflow(0, sz[N - 1] - 1);
    cout << ans << endl;
}