結果

問題 No.654 Air E869120
コンテスト
ユーザー n0ma_ru
提出日時 2024-07-22 03:20:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 4,149 bytes
コンパイル時間 2,895 ms
コンパイル使用メモリ 217,340 KB
最終ジャッジ日時 2025-02-23 17:43:38
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ALL(v) v.begin(),v.end()
#define dbg(x) cerr << #x << ": " << (x) << endl;
template<class F, class S>
ostream& operator<<(ostream& os, pair<F,S>& p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template<class Iter>
void print(Iter beg, Iter end) {
    for (Iter itr = beg; itr != end; ++itr) {
        cerr << *itr << ' ';
    }
    cerr << '\n';
}
inline bool naraba(bool a, bool b) { return (!a || b); }

struct maxflow
{
    struct edge {int to, rep; long long cap;};
    std::vector<std::vector<edge>> g;
    std::vector<int> dis, id;
    public:
    maxflow(int n) : g(n), id(n), dis(n) {}
    void add_edge(int s, int t, long long f)
    {
		assert(0 <= s && s < g.size());
		assert(0 <= t && t < g.size());
        g[s].push_back({t, (int)g[t].size(), f});
        g[t].push_back({s, (int)g[s].size() - 1, 0});
    }
    long long flow(int s, int t)
    {
		assert(0 <= s && s < g.size());
		assert(0 <= t && t < g.size());
        long long ret = 0;
        while (true)
        {
            bfs(s);
            if (dis[t] <= dis[s]) return ret;
            id.assign(id.size(), 0);
            long long val;
            while ((val = path(s, t)) > 0) ret += val;
        }
    }
    private:
    void bfs(int s)
    {
        dis.assign(g.size(), -1);
        dis[s] = 0;
        std::queue<int> q;
        for (q.push(s); !q.empty(); q.pop())
        {
            int now = q.front();
            for (auto &v : g[now])
            {
                if (v.cap > 0 && dis[v.to] < 0)
                {
                    dis[v.to] = dis[now] + 1;
                    q.push(v.to);
                }
            }
        }
    }
    long long path(int s, int t)
    {
        const long long inf = (1LL << 60);
        std::stack<edge> st;
        long long ret = inf;
        st.push({s, -1, inf});
        while (!st.empty())
        {
            auto now = st.top();
            st.pop();
            if (now.rep == -1)
            {
                if (now.to == t)
                {
                    ret = now.cap;
                    break;
                }
                for (int &i = id[now.to]; i < g[now.to].size(); ++i)
                {
                    auto &e = g[now.to][i];
                    if (dis[e.to] > dis[now.to] && e.cap > 0)
                    {
                        st.push({e.to, e.rep, 0});
                        st.push({e.to, -1, std::min(e.cap, now.cap)});
                    }
                }
            }
        }
        if (ret == inf) return 0;
        int now = t;
        while (now != s)
        {
            while (!st.empty() && st.top().to != now) st.pop();
            edge &v1 = st.top(), &v2 = g[v1.to][v1.rep];
            v2.cap += ret;
            g[v2.to][v2.rep].cap -= ret;
            now = v2.to;
        }
        return ret;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20); cerr << fixed << setprecision(6);
    ll n,m,d;
    cin >> n >> m >> d;
    ll inf = 1e18;
    vector<pair<ll,ll>> v(1, make_pair(n-1,inf));
    vector<array<ll,5>> e(m);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < 5; ++j) {
            cin >> e[i][j];
        }
        --e[i][0]; --e[i][1];
        if (e[i][1] != n-1) e[i][3] += d;
        v.emplace_back(e[i][0], e[i][2]);
    }
    sort(ALL(v));
    v.erase(unique(ALL(v)), v.end());
    // print(ALL(v));
    maxflow mf(v.size());
    // flight
    for (auto [f,t,p,q,w] : e) {
        int from = lower_bound(ALL(v), make_pair(f, p)) - v.begin();
        int to = lower_bound(ALL(v), make_pair(t, q)) - v.begin();
        if (to < v.size() && v[to].first == t) {
            mf.add_edge(from, to, w);
        }
    }
    // time
    for (int i = 1; i < v.size(); ++i) {
        if (v[i].first == v[i-1].first) {
            mf.add_edge(i-1, i, inf);
        }
    }

    // print(ALL(v));
    ll ans = 0;
    if (v.front().first == 0 && v.back().first == n-1) {
        ans = mf.flow(0, v.size()-1);
    }
    cout << ans << '\n';
}
0