結果

問題 No.654 Air E869120
ユーザー 0w10w1
提出日時 2018-04-16 21:31:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 2,804 bytes
コンパイル時間 2,627 ms
コンパイル使用メモリ 219,048 KB
実行使用メモリ 15,856 KB
最終ジャッジ日時 2023-09-09 10:57:29
合計ジャッジ時間 4,676 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 5 ms
4,656 KB
testcase_11 AC 6 ms
4,956 KB
testcase_12 AC 5 ms
4,920 KB
testcase_13 AC 5 ms
4,920 KB
testcase_14 AC 6 ms
5,004 KB
testcase_15 AC 6 ms
4,936 KB
testcase_16 AC 39 ms
15,808 KB
testcase_17 AC 38 ms
15,856 KB
testcase_18 AC 38 ms
15,676 KB
testcase_19 AC 40 ms
15,680 KB
testcase_20 AC 31 ms
10,040 KB
testcase_21 AC 31 ms
9,744 KB
testcase_22 AC 29 ms
9,612 KB
testcase_23 AC 30 ms
9,876 KB
testcase_24 AC 31 ms
9,844 KB
testcase_25 AC 29 ms
9,752 KB
testcase_26 AC 29 ms
9,780 KB
testcase_27 AC 25 ms
6,996 KB
testcase_28 AC 25 ms
6,712 KB
testcase_29 AC 25 ms
6,436 KB
testcase_30 AC 21 ms
4,380 KB
testcase_31 AC 21 ms
4,376 KB
testcase_32 AC 21 ms
4,380 KB
testcase_33 AC 21 ms
4,380 KB
testcase_34 AC 20 ms
4,376 KB
testcase_35 AC 2 ms
4,376 KB
testcase_36 AC 2 ms
4,376 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 <bits/stdc++.h>
using namespace std;

template <typename T, T inf>
struct Dinic {
  static const int MAXV = 10000;
  T INF = inf;
  struct Edge {
    int v;
    T f;
    int re;
    Edge(int _v, T _f, int _re) : v(_v), f(_f), re(_re) {}
  };
  int n, s, t, level[MAXV];
  vector<Edge> E[MAXV];
  int now[MAXV];
  Dinic(int _n, int _s, int _t) : n(_n), s(_s), t(_t) {}
  void add_edge(int u, int v, T f, bool bidirectional = false) {
    E[u].emplace_back(v, f, E[v].size());
    E[v].emplace_back(u, 0, E[u].size() - 1);
    if (bidirectional) {
      E[v].emplace_back(u, f, E[u].size() - 1);
    }
  }
  bool BFS() {
    memset(level, -1, sizeof(level));
    queue<int> que;
    que.emplace(s);
    level[s] = 0;
    while (que.size()) {
      int u = que.front();
      que.pop();
      for (auto it : E[u]) {
        if (it.f > 0 && level[it.v] == -1) {
          level[it.v] = level[u] + 1;
          que.emplace(it.v);
        }
      }
    }
    return level[t] != -1;
  }
  T DFS(int u, T nf) {
    if (u == t) return nf;
    T res = 0;
    while (now[u] < E[u].size()) {
      Edge &it = E[u][now[u]];
      if (it.f > 0 && level[it.v] == level[u] + 1) {
        T tf = DFS(it.v, min(nf, it.f));
        res += tf;
        nf -= tf;
        it.f -= tf;
        E[it.v][it.re].f += tf;
        if (nf == 0) return res;
      } else
        ++now[u];
    }
    if (!res) level[u] = -1;
    return res;
  }
  T flow(T res = 0) {
    while (BFS()) {
      T temp;
      memset(now, 0, sizeof(now));
      while (temp = DFS(s, INF)) {
        res += temp;
        res = min(res, INF);
      }
    }
    return res;
  }
};

signed main() {
  ios::sync_with_stdio(false);

  int N, M, D;
  cin >> N >> M >> D;

  vector<int> U(M), V(M), P(M), Q(M), W(M);
  map<pair<int, int>, int> id;
  id[make_pair(0, 0)] = 0;
  id[make_pair(N - 1, int(2e9))] = 1;
  for (int i = 0; i < M; ++i) {
    cin >> U[i] >> V[i] >> P[i] >> Q[i] >> W[i];
    --U[i];
    --V[i];
    if (!id.count(make_pair(U[i], P[i]))) {
      int x = id.size();
      id[make_pair(U[i], P[i])] = x;
    }
    if (!id.count(make_pair(V[i], Q[i] + D))) {
      int x = id.size();
      id[make_pair(V[i], Q[i] + D)] = x;
    }
  }

  Dinic<int64_t, 1LL << 60> din(id.size(), 0, 1);
  for (auto it = id.begin(); it != id.end(); ++it) {
    for (auto jt = next(it); jt != id.end(); ++jt) {
      if ((it->first).first == (jt->first).first) {
        int x = it->second;
        int y = jt->second;
        if ((it->first).second > (jt->first).second) {
          swap(x, y);
        }
        din.add_edge(x, y, din.INF);
      }
    }
  }
  for (int i = 0; i < M; ++i) {
    int x = id[make_pair(U[i], P[i])];
    int y = id[make_pair(V[i], Q[i] + D)];
    din.add_edge(x, y, W[i]);
  }

  cout << din.flow() << endl;

  return 0;
}
0