結果

問題 No.654 Air E869120
コンテスト
ユーザー boutarou
提出日時 2021-10-01 10:39:56
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 2,777 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,874 ms
コンパイル使用メモリ 214,016 KB
最終ジャッジ日時 2025-01-24 18:49:33
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘void Dinic::addEdge(ll, ll, ll)’:
main.cpp:8:22: warning: narrowing conversion of ‘(&((Dinic*)this)->Dinic::G.std::vector<std::vector<Dinic::Edge> >::operator[](((std::vector<std::vector<Dinic::Edge> >::size_type)to)))->std::vector<Dinic::Edge>::size()’ from ‘std::vector<Dinic::Edge>::size_type’ {aka ‘long unsigned int’} to ‘ll’ {aka ‘long long int’} [-Wnarrowing]
    8 | #define len(s) s.size()
      |                      ^
main.cpp:17:37: note: in expansion of macro ‘len’
   17 |         G[from].push_back({to, cap, len(G[to])});
      |                                     ^~~
main.cpp:18:48: warning: narrowing conversion of ‘((&((Dinic*)this)->Dinic::G.std::vector<std::vector<Dinic::Edge> >::operator[](((std::vector<std::vector<Dinic::Edge> >::size_type)from)))->std::vector<Dinic::Edge>::size() - 1)’ from ‘std::vector<Dinic::Edge>::size_type’ {aka ‘long unsigned int’} to ‘ll’ {aka ‘long long int’} [-Wnarrowing]
   18 |         G[to].push_back({from, 0, len(G[from]) - 1});
      |                                                ^

ソースコード

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>;

ll inf = 1e13;
#define len(s) s.size()

struct Dinic {
    struct Edge {
        ll to, cap, rev;
    };
    vector<vector<Edge>> G;
    vector<ll> level, iter;
    void addEdge(ll from, ll to, ll cap) {
        G[from].push_back({to, cap, len(G[to])});
        G[to].push_back({from, 0, len(G[from]) - 1});
    }
    void bfs(ll s) {
        fill(level.begin(), level.end(), -1);
        level[s] = 0;
        queue<ll> que;
        que.push(s);
        while(len(que)) {
            ll p = que.front();
            que.pop();
            for(Edge e : G[p]) {
                if(e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[p] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    ll dfs(ll v, ll t, ll f) {
        if(v == t) return f;
        for(ll &i = iter[v]; i < len(G[v]); i++) {
            Edge &e = G[v][i];
            if(e.cap > 0 && level[e.to] > level[v]) {
                ll d = dfs(e.to, t, min(f, e.cap));
                if(d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    ll maxFlow(ll s, ll t) {
        ll flow = 0;
        while(1) {
            bfs(s);
            if(level[t] < 0) return flow;
            fill(iter.begin(), iter.end(), 0);
            ll f = 0;
            while((f = dfs(s, t, inf)) > 0) {
                flow += f;
            }
        }
    }
    Dinic(ll N)
        : G(N), level(N), iter(N) {
    }
};

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;
    Dinic mf(sum[n]);
    rep(i, n) {
        rep(j, g[i].size() - 1) {
            mf.addEdge(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.addEdge(from, to, w[i]);
    }
    cout << mf.maxFlow(0, sum[n] - 1) << endl;

    return 0;
}
0