結果

問題 No.654 Air E869120
ユーザー pekempeypekempey
提出日時 2018-02-23 22:57:06
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,089 bytes
コンパイル時間 563 ms
コンパイル使用メモリ 70,188 KB
最終ジャッジ日時 2024-04-27 02:31:46
合計ジャッジ時間 1,294 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In member function 'T MaxFlow<T>::calc(int, int)':
main.cpp:37:34: error: 'numeric_limits' is not a member of 'std'
   37 |       while ((f = dfs(s, t, std::numeric_limits<T>::max())) > 0) sum += f;
      |                                  ^~~~~~~~~~~~~~
main.cpp:37:50: error: expected primary-expression before '>' token
   37 |       while ((f = dfs(s, t, std::numeric_limits<T>::max())) > 0) sum += f;
      |                                                  ^
main.cpp:37:56: error: no matching function for call to 'max()'
   37 |       while ((f = dfs(s, t, std::numeric_limits<T>::max())) > 0) sum += f;
      |                                                   ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:50,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/iostream:39,
                 from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
main.cpp:37:56: note:   candidate expects 2 arguments, 0 provided
   37 |       while ((f = dfs(s, t, std::numeric_limits<T>::max())) > 0) sum += f;
      |                                                   ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/s

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>

using namespace std;

template<typename T>
class MaxFlow {
private:
  struct Edge {
    int v;
    int r;
    T c;
  };

private:
  std::vector<std::vector<Edge>> g;
  std::vector<int> d, it;

public:
  MaxFlow(int n) : g(n), d(n), it(n) {}

  void add(int u, int v, T c) {
    const int i = g[u].size();
    const int j = g[v].size();
    g[u].push_back({ v, j, c });
    g[v].push_back({ u, i, 0 });
  }

  T calc(int s, int t) {
    T sum = 0;
    while (bfs(s, t)) {
      T f;
      while ((f = dfs(s, t, std::numeric_limits<T>::max())) > 0) sum += f;
    }
    return sum;
  }

private:
  bool bfs(int s, int t) {
    std::fill(it.begin(), it.end(), 0);
    std::fill(d.begin(), d.end(), -1);
    d[s] = 0;
    std::queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (Edge e : g[v]) {
        if (e.c > 0 && d[e.v] == -1) {
          d[e.v] = d[v] + 1;
          q.push(e.v);
        }
      }
    }
    return d[t] >= 0;
  }

  T dfs(int v, int t, T f) {
    if (v == t) return f;
    while (it[v] < g[v].size()) {
      Edge &e = g[v][it[v]++];
      if (e.c > 0 && d[v] < d[e.v]) {
        T ff = dfs(e.v, t, std::min(f, e.c));
        if (ff > 0) {
          e.c -= ff;
          g[e.v][e.r].c += ff;
          return ff;
        }
      }
    }
    return 0;
  }
};

int main() {
  int n, m, d;
  cin >> n >> m >> d;

  MaxFlow<long long> mf(m * 2 + 2);
  int src = m * 2;
  int sink = m * 2 + 1;

  vector<int> u(m), v(m), p(m), q(m), w(m);
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i];
    u[i]--;
    v[i]--;
  }
  for (int i = 0; i < m; i++) {
    if (u[i] == 0) {
      mf.add(src, i, 1e15);
    }
    if (v[i] == n - 1) {
      mf.add(i + m, sink, 1e15);
    }
    mf.add(i, i + m, w[i]);
    for (int j = 0; j < m; j++) if (i != j) {
      if (v[i] == u[j] && q[i] + d <= p[j]) {
        mf.add(i + m, j, 1e15);
      }
    }
  }
  cout << mf.calc(src, sink) << endl;
}
0