結果

問題 No.654 Air E869120
コンテスト
ユーザー boutarou
提出日時 2021-10-01 10:30:20
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 2,449 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,507 ms
コンパイル使用メモリ 210,900 KB
最終ジャッジ日時 2025-01-24 18:49:22
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 4
other AC * 5 TLE * 8 MLE * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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