結果

問題 No.654 Air E869120
ユーザー boutarouboutarou
提出日時 2021-10-01 10:43:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 2,455 bytes
コンパイル時間 2,536 ms
コンパイル使用メモリ 216,600 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-25 21:07:59
合計ジャッジ時間 4,181 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 9 ms
4,380 KB
testcase_11 AC 6 ms
4,376 KB
testcase_12 AC 6 ms
4,380 KB
testcase_13 AC 6 ms
4,376 KB
testcase_14 AC 6 ms
4,380 KB
testcase_15 AC 6 ms
4,380 KB
testcase_16 AC 9 ms
4,380 KB
testcase_17 AC 8 ms
4,376 KB
testcase_18 AC 7 ms
4,376 KB
testcase_19 AC 10 ms
4,376 KB
testcase_20 AC 4 ms
4,376 KB
testcase_21 AC 5 ms
4,380 KB
testcase_22 AC 4 ms
4,376 KB
testcase_23 AC 4 ms
4,376 KB
testcase_24 AC 5 ms
4,380 KB
testcase_25 AC 4 ms
4,376 KB
testcase_26 AC 4 ms
4,380 KB
testcase_27 AC 4 ms
4,380 KB
testcase_28 AC 4 ms
4,376 KB
testcase_29 AC 4 ms
4,376 KB
testcase_30 AC 4 ms
4,376 KB
testcase_31 AC 4 ms
4,376 KB
testcase_32 AC 4 ms
4,380 KB
testcase_33 AC 4 ms
4,380 KB
testcase_34 AC 4 ms
4,380 KB
testcase_35 AC 2 ms
4,376 KB
testcase_36 AC 2 ms
4,380 KB
testcase_37 AC 2 ms
4,376 KB
testcase_38 AC 1 ms
4,376 KB
testcase_39 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < int(n); i++)
using ll = long long;
using P = pair<int, int>;

// Ford-Fulkerson
template <typename T>
class max_flow {
public:
    struct edge {
        int to;
        T cap;
        int rev;
    };

    int n;
    vector<vector<edge>> g;
    vector<bool> used;
    max_flow(int n = 0)
        : n(n), g(n), used(n) {
    }
    void add_edge(int from, int to, T cap) {
        g[from].push_back((edge){to, cap, int(g[to].size())});
        g[to].push_back((edge){from, 0LL, int(g[from].size() - 1)});
    }
    T dfs(int v, int goal_v, T flow) {
        if(v == goal_v) return flow;
        used[v] = true;
        for(int i = 0; i < (int)g[v].size(); i++) {
            edge &e = g[v][i];
            if(!used[e.to] && e.cap > 0) {
                T next_flow = dfs(e.to, goal_v, min(flow, e.cap));
                if(next_flow > 0) {
                    e.cap -= next_flow;
                    g[e.to][e.rev].cap += next_flow;
                    return next_flow;
                }
            }
        }
        return 0;
    }
    T calc(int s, int t, T ma = numeric_limits<T>::max()) {
        T flow = 0;
        while(1) {
            used = vector<bool>(n, false);
            T f = dfs(s, t, ma);
            if(f == 0) return flow;
            flow += f;
        }
    }
};

int main() {
    int n, m, d;
    cin >> n >> m >> d;
    vector<int> u(m), v(m), p(m), q(m);
    vector<ll> w(m);
    rep(i, m) cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i];
    rep(i, m) u[i]--, v[i]--, q[i] += d;
    vector<vector<int>> g(n);
    rep(i, m) {
        g[u[i]].push_back(p[i]);
        g[v[i]].push_back(q[i]);
    }
    g[0].push_back(0);
    g[n - 1].push_back(2e9 + 1);
    rep(i, n) sort(g[i].begin(), g[i].end());
    rep(i, n) g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
    vector<int> sum(n + 1);
    rep(i, n) sum[i + 1] = sum[i] + g[i].size();

    ll INF = 1e13;
    max_flow<ll> mf(sum[n]);
    rep(i, n) {
        rep(j, g[i].size() - 1) {
            mf.add_edge(sum[i] + j, sum[i] + j + 1, INF);
        }
    }
    rep(i, m) {
        int from = sum[u[i]] + (lower_bound(g[u[i]].begin(), g[u[i]].end(), p[i]) - g[u[i]].begin());
        int to = sum[v[i]] + (lower_bound(g[v[i]].begin(), g[v[i]].end(), q[i]) - g[v[i]].begin());
        mf.add_edge(from, to, w[i]);
    }
    cout << mf.calc(0, sum[n] - 1, 1e13) << endl;

    return 0;
}
0