結果

問題 No.654 Air E869120
ユーザー boutarouboutarou
提出日時 2021-10-01 10:30:20
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 2,449 bytes
コンパイル時間 2,343 ms
コンパイル使用メモリ 218,668 KB
実行使用メモリ 497,204 KB
最終ジャッジ日時 2024-07-18 16:39:59
合計ジャッジ時間 15,784 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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)
        : 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