#238504 (C++17) No.654 Air E869120

• 問題: No.654 Air E869120
• ユーザー: 夕叢霧香(ゆうむらきりか)
• 提出日時: 2018-02-23 23:38:17
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 25 ms / 2,000 ms
• コード長: 8,111 bytes
• コンパイル時間: 1,714 ms
• コンパイル使用メモリ: 113,968 KB
• 最終ジャッジ日時: 2025-01-05 08:39:22
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 5
other	AC * 35

ソースコード

#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
#include<cassert>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)
// https://gist.github.com/MiSawa/9645253
#define REP(i, b, n) for(int i = (b); i < (n); ++i)
#define let(v, x) __typeof(x) v = (x)
#define foreach(i,v) for(let(i, (v).begin());i!=(v).end();i++)

/**
 * 割とどうしてくれてもいいけど, 理解 && バグ潰ししてから使うべきです.
 *
 */

/**
 * Dinic と同じように,
 * - 頂点数を取るコンストラクタ
 * - add_edge(src, dst, cap)
 * - run(s, t)
 * の 3 つを備えるクラス (例えば MyDinic) を作って,
 *
 * Benchmark<Dinic> bm
 * を
 * Benchmark<Dinic, MyDinic> bm
 * とかに変えれば, 比較出来る.
 */

struct Dinic{//{{{
    typedef lint Cap;
    static const Cap INF = 1e16;
    struct E{//{{{
        int dst;
        Cap cap;
        int rev;
        E(int dst, Cap cap, int rev) : dst(dst), cap(cap), rev(rev) {}
    };//}}}
    int n;
    vector<vector<E> > g;
    Dinic(int n) : n(n), g(n) {}
    inline void add_edge(int src, int dst, Cap cap){//{{{
        if(src == dst) return;
        g[src].push_back(E(dst,cap,g[dst].size()));
        g[dst].push_back(E(src, 0 ,g[src].size() - 1));
    }//}}}
    inline void add_undirected_edge(int src, int dst, Cap cap){//{{{
        if(src == dst) return;
        g[src].push_back(E(dst,cap,g[dst].size()));
        g[dst].push_back(E(src,cap,g[src].size() - 1));
    }//}}}

    vector<int> level, iter;
    Cap dfs(const int &s, const int &u, Cap crr){//{{{
        if(s == u || crr == 0) return crr;
        Cap sum = 0;
        for(int &i = iter[u]; i < g[u].size(); ++i){
            E &e = g[u][i], &ee = g[e.dst][e.rev];
            const int &v = e.dst; // s -- v - u -- t
            if(level[v] >= level[u] || ee.cap <= 0) continue;
            Cap f = dfs(s, v, min(crr - sum, ee.cap));
            if(f <= 0) continue;
            ee.cap -= f; e.cap += f;
            sum += f;
            if(sum == crr) break;
        }
        return sum;
    }//}}}
    Cap run(int s, int t){//{{{
        vector<int> q(n);
        for(Cap flow = 0; ;){
            level.assign(n, -1);
            int ql = 0, qr = 0;
            level[q[qr++] = s] = 0;
            while(ql != qr && level[t] == -1){
                int u = q[ql++];
                foreach(e, g[u]) if(e->cap > 0 && level[e->dst] == -1)
                    level[ q[qr++] = e->dst ] = level[u] + 1;
            }
            if(level[t] == -1) return flow;
            iter.assign(n, 0);
            flow += dfs(s, t, INF);
        }
    }//}}}
};//}}}

struct Wave{//{{{
    typedef lint Cap;
    static const Cap INF = 1e16;
    struct E{//{{{
        int src, dst;
        Cap cap, _cap;
        int rev;
        E(int src, int dst, Cap cap, int rev) :
            src(src), dst(dst), cap(cap), _cap(0), rev(rev) {}
    };//}}}
    int n;
    vector<vector<E> > g;
    Wave(int n) : n(n), g(n) {}
    inline void add_edge(int src, int dst, Cap cap){//{{{
        if(src == dst) return;
        g[src].push_back(E(src, dst,cap,g[dst].size()));
        g[dst].push_back(E(dst, src, 0 ,g[src].size() - 1));
    }//}}}

    inline E &rev(const E& e){ return g[e.dst][e.rev]; }
    vector<int> level, iter;
    vector<int> blocked;
    vector<int> unbalance[2]; // { unblocked, blocked }
    vector<int> inS;
    vector<Cap> ex;
    inline void push(E &e){//{{{
        Cap f = min(e.cap, ex[e.src]);
        if(!inS[e.dst]) unbalance[blocked[e.dst]].push_back(e.dst);
        inS[e.dst] = true;
        e.cap -= f; rev(e).cap += f;
        ex[e.src] -= f; ex[e.dst] += f;
    }//}}}
    // dir = +1 ? s to t : t to s
    inline void discharge(const int& u, const int dir){//{{{
        for(int &i = iter[u]; i < g[u].size(); ++i){
            E &e = g[u][i];
            if(e.cap == 0 || level[e.src] + dir != level[e.dst]) continue;
            if(dir == +1 && blocked[e.dst]) continue;
            push(e);
            if(ex[u] == 0) return;
        }
        blocked[u] = true;
        if(!inS[u]) unbalance[1].push_back(u);
        inS[u] = true;
        iter[u] = 0;
    }//}}}
    Cap run(int s, int t){//{{{
        vector<int> q(n);
        vector<int> tmp; tmp.reserve(n);
        rep(i, 2) unbalance[i].reserve(n);
        rep(i, 2) unbalance[i].clear();
        inS.assign(n, false); inS[s] = inS[t] = true;
        for(Cap flow = 0; ;){
            level.assign(n, -1);
            int ql = 0, qr = 0;
            level[q[qr++] = s] = 0;
            while(ql != qr && level[t] == -1){
                const int &u = q[ql++];
                foreach(e, g[u]) if(level[e->dst] == -1 && e->cap + e->_cap > 0)
                    level[ q[qr++] = e->dst ] = level[u] + 1;
            }
            if(level[t] == -1) return flow;

            rep(i, qr){
                if(level[q[i]] == level[t] && q[i] != t){
                    level[q[i]] = -1; continue;
                }
                foreach(e, g[q[i]]){
                    if(level[e->src] + 1 == level[e->dst]){
                        e->cap += e->_cap; e->_cap = 0;
                    }else{
                        e->_cap += e->cap; e->cap = 0;
                    }
                }
            }

            iter.assign(n, 0);
            blocked.assign(n, false);
            ex.assign(n, 0); ex[s] = INF; discharge(s, +1); ex[s] = 0;

            while(!unbalance[0].empty() || !unbalance[1].empty()){
                rep(b, 2) while(!unbalance[b].empty()){
                    tmp.clear();
                    int l = level[unbalance[b].back()];
                    while(!unbalance[b].empty() && level[unbalance[b].back()] == l){
                        int v = unbalance[b].back(); unbalance[b].pop_back();
                        inS[v] = false; tmp.push_back(v);
                    }
                    foreach(v, tmp) discharge(*v, b ? -1 : +1);
                }
            }
            flow += ex[t];
        }
    }//}}}
};//}}}


const lint INF=1e16;


typedef pair<int,pii> pipii;
map<pipii,int> memo;

int get(int v,pii t){
  pipii ind(v,t);
  if(memo.count(ind))return memo[ind];
  int s=memo.size();
  memo[ind]=s;
  return s;
}


const int A=1000;
vector<pii> leave[A];
vector<pii> arrive[A];

int u[A],v[A],p[A],q[A],w[A];

int main(){
  int n,m,d;
  cin>>n>>m>>d;
  vector<pii>test;
  rep(i,m){
    cin>>u[i]>>v[i]>>p[i]>>q[i]>>w[i];
    u[i]--,v[i]--;
    leave[u[i]].push_back(pii(p[i],i));
    arrive[v[i]].push_back(pii(q[i],i));
    test.push_back(pii(p[i],-(i+1)));
    test.push_back(pii(q[i],i+1));
    get(u[i],pii(p[i],i));
    get(n+v[i],pii(q[i],i));
  }
#if 0
  sort(test.begin(),test.end());
  rep(i,test.size()){
    int idx=test[test.size()-1-i].second;
    int j=abs(idx)-1;
    if(idx>0){
      get(u[j],pii(p[j],j));
    }
  }
  rep(i,test.size()){
    int idx=test[test.size()-1-i].second;
    int j=abs(idx)-1;
    if(idx<0){
      get(v[j],pii(q[j],j));
    }
  }
#endif
  int tn=memo.size()+2;
  Dinic din(tn);
  rep(i,n){
    sort(leave[i].begin(),leave[i].end());
    sort(arrive[i].begin(),arrive[i].end());
  }
  rep(i,n){
    rep(j,leave[i].size()-1){
      int a=get(i,leave[i][j]);
      int b=get(i,leave[i][j+1]);
      din.add_edge(a,b,INF);
    }
    rep(j,arrive[i].size()){
      int a=get(n+i,arrive[i][j]);
      lint time=arrive[i][j].first;
      lint dst=time+d;
      if(dst>1e9)continue;
      int idx=lower_bound(leave[i].begin(),leave[i].end(),pii((int)dst,-1))-leave[i].begin();
      if(idx<(int)leave[i].size()){
	int b=get(i,leave[i][idx]);
	din.add_edge(a,b,INF);
      }
    }
  }
  rep(i,m){
    int a=get(u[i],pii(p[i],i));
    int b=get(n+v[i],pii(q[i],i));
    din.add_edge(a,b,w[i]);
  }
  int src=tn-2;
  int sink=tn-1;
  rep(i,arrive[n-1].size()){
    int a=get(n+n-1,arrive[n-1][i]);
    din.add_edge(a,sink,INF);
  }
  rep(i,leave[0].size()){
    int a=get(0,leave[0][i]);
    din.add_edge(src,a,INF);
  }
  lint flow=din.run(src,sink);
  cout<<flow<<endl;
}