結果

問題 No.654 Air E869120
ユーザー face4face4
提出日時 2019-12-16 13:02:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 2,319 bytes
コンパイル時間 893 ms
コンパイル使用メモリ 86,116 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-15 17:32:59
合計ジャッジ時間 3,315 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

struct edge{
    int to;
    ll cap;
    int rev;
};

#define MAX_V 5000
vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from, int to, ll cap){
    G[from].push_back((edge){to, cap, (int)G[to].size()});
    G[to].push_back((edge){from, 0, (int)G[from].size()-1});
}

// v...target vertex, t...end vertex, f...maximum flow 
ll dfs(int v, int t, ll f){
    if(v == t)  return f;

    used[v] = true;
    for(int i = 0; i < G[v].size(); i++){
        edge &e = G[v][i];
        if(!used[e.to] && e.cap > 0){
            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;
}

const ll INF = 1ll<<60;

// maxflow from s to t
ll max_flow(int s, int t){
    ll flow = 0;
    while(1){
        memset(used, 0, sizeof(used));
        ll f = dfs(s, t, INF);
        if(f == 0)  return flow;
        flow += f;
    }
}

typedef pair<int,int> pii;

int main(){
    int n, m, d;
    cin >> n >> m >> d;
    vector<int> tim[n], u(m), v(m), p(m), q(m), w(m);
    tim[0].push_back(0);
    tim[n-1].push_back(1e9);
    for(int i = 0; i < m; i++){
        cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i];
        u[i]--, v[i]--;
        q[i] += (v[i]==n-1 ? 0 : d);
        if(q[i] > 1e9)  continue;
        tim[u[i]].push_back(p[i]);
        tim[v[i]].push_back(q[i]);
    }
    vector<pii> vp;
    for(int i = 0; i < n; i++){
        if(tim[i].size() == 0)  continue;
        sort(tim[i].begin(), tim[i].end());
        tim[i].erase(unique(tim[i].begin(),tim[i].end()),tim[i].end());
        for(int j : tim[i]){
            vp.push_back({i, j});
        }
    }
    auto f = [&](int i, int j)->int{
        return lower_bound(vp.begin(),vp.end(),make_pair(i,j))-vp.begin();
    };
    // 待機
    for(int i = 0; i < n; i++){
        for(int j = 0; j+1 < tim[i].size(); j++){
            add_edge(f(i,tim[i][j]), f(i,tim[i][j+1]), INF);
        }
    }
    // 移動
    for(int i = 0; i < m; i++){
        if(q[i] > 1e9)  continue;
        add_edge(f(u[i], p[i]), f(v[i], q[i]), w[i]);
    }
    cout << max_flow(f(0, 0), f(n-1, 1e9)) << endl;
    return 0;
}
0