結果
| 問題 |
No.654 Air E869120
|
| コンテスト | |
| ユーザー |
 ats5515
|
| 提出日時 | 2018-02-23 23:47:00 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 3,983 bytes |
| コンパイル時間 | 931 ms |
| コンパイル使用メモリ | 90,016 KB |
| 最終ジャッジ日時 | 2024-11-14 20:21:04 |
| 合計ジャッジ時間 | 1,600 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In constructor ‘Dinic::Dinic(const Graph&)’:
main.cpp:35:42: error: ‘numeric_limits’ was not declared in this scope
35 | g(n, vector<int>()), inf(numeric_limits<Capacity>::max() / 8) {
| ^~~~~~~~~~~~~~
main.cpp:35:65: error: expected primary-expression before ‘>’ token
35 | g(n, vector<int>()), inf(numeric_limits<Capacity>::max() / 8) {
| ^
main.cpp:35:71: error: no matching function for call to ‘max()’
35 | g(n, vector<int>()), inf(numeric_limits<Capacity>::max() / 8) {
| ~~~~~^~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
from /usr/include/c++/11/ios:40,
from /usr/include/c++/11/ostream:38,
from /usr/include/c++/11/iostream:39,
from main.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: ‘template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)’
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
main.cpp:35:71: note: candidate expects 2 arguments, 0 provided
35 | g(n, vector<int>()), inf(numeric_limits<Capacity>::max() / 8) {
| ~~~~~^~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
from /usr/include/c++/11/ios:40,
from /usr/include/c++/11/ostream:38,
from /usr/include/c++/11/iostream:39,
from main.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: ‘template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
300 | max(const _Tp& __a
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
int INF = (int)1 << 60;
typedef int Capacity;
struct Edge {
int src, dst;
Capacity cap;
Edge(int src_, int dst_, Capacity cap_) :
src(src_), dst(dst_), cap(cap_) { }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
struct Dinic {
int n, s, t;
vector<int> level, prog, que;
vector<vector<Capacity>> cap, flow;
vector<vector<int>> g;
Capacity inf;
Dinic(const Graph &graph)
: n(graph.size()),
cap(n, vector<Capacity>(n)), flow(n, vector<Capacity>(n)),
g(n, vector<int>()), inf(numeric_limits<Capacity>::max() / 8) {
for (int i = 0; i < n; i++) {
for (auto &e : graph[i]) {
int u = e.src, v = e.dst;
Capacity c = e.cap;
cap[u][v] += c; cap[v][u] += c; flow[v][u] += c;
g[u].push_back(v); g[v].push_back(u);
}
}
}
inline Capacity residue(int u, int v) { return cap[u][v] - flow[u][v]; }
Capacity solve(int s_, int t_) {
this->t = t_, this->s = s_;
que.resize(n + 1);
Capacity res = 0;
while (levelize()) { prog.assign(n, 0); res += augment(s, inf); }
return res;
}
bool levelize() {
int l = 0, r = 0;
level.assign(n, -1); level[s] = 0; que[r++] = s;
while (l != r) {
int v = que[l++]; if (v == t) break;
for (const int &d : g[v]) if (level[d] == -1 && residue(v, d) != 0) {
level[d] = level[v] + 1; que[r++] = d;
}
}
return level[t] != -1;
}
Capacity augment(int v, Capacity lim) {
Capacity res = 0;
if (v == t) return lim;
for (int &i = prog[v]; i < (int)g[v].size(); i++) {
const int &d = g[v][i];
if (residue(v, d) == 0 || level[v] >= level[d]) continue;
const Capacity aug = augment(d, min(lim, residue(v, d)));
flow[v][d] += aug; flow[d][v] -= aug;
res += aug; lim -= aug;
if (lim == 0) break;
}
return res;
}
}; signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N, M, d;
cin >> N >> M >> d;
Graph g(2 * M + 2);
vector<int> A(N);
vector<vector<pair<int, int> > >ii(N);
vector<vector<pair<int, int> > >oo(N);
vector<int> u(M);
vector<int> v(M);
vector<int> p(M);
vector<int> q(M);
vector<int> w(M);
for (int i = 0; i < M; i++) {
cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i];
u[i]--;
v[i]--;
oo[u[i]].push_back(make_pair(p[i], i));
ii[v[i]].push_back(make_pair(q[i], i));
}
for (int i = 0; i < M; i++) {
g[i].emplace_back(i, i + M, w[i]);
}
for (int i = 0; i < N; i++) {
//cerr << i << endl;
sort(oo[i].begin(), oo[i].end());
sort(ii[i].begin(), ii[i].end());
for (int j = 0; j < (int)oo[i].size() - 1; j++) {
g[oo[i][j].second].emplace_back(oo[i][j].second, oo[i][j + 1].second, INF);
}
//cerr << i << endl;
int x = 0;
for (int j = 0; j < (int)ii[i].size(); j++) {
//cerr << x << endl;
//cerr << oo[i].size() << endl;
//cerr << i << " " << j << endl;
//cerr << ii[i][j].first << endl;
//cerr << oo[i][x].first << endl;
while (x < (int)oo[i].size() && (oo[i][x].first < ii[i][j].first + d)) {
x++;
//cerr << x << endl;
}
//cerr << x << endl;
//cerr << j << endl;
if (x < (int)oo[i].size()) {
g[ii[i][j].second + M].emplace_back(ii[i][j].second + M, oo[i][x].second, INF);
}
//cerr << j << endl;
}
}
if ((int)oo[0].size() == 0) {
cout << 0 << endl;
return 0;
}
if ((int)ii[N - 1].size() == 0) {
cout << 0 << endl;
return 0;
}
for (int i = 0; i < oo[0].size(); i++) {
g[2 * M].emplace_back(2 * M, oo[0][i].second, INF);
}
for (int i = 0; i < ii[N - 1].size(); i++) {
g[ii[N - 1][i].second + M].emplace_back(ii[N - 1][i].second + M, 2 * M + 1, INF);
}
/*for (int i = 0; i < g.size(); i++) {
for (int j = 0; j < g[i].size(); j++) {
cout << i << " " << g[i][j].dst << " " << g[i][j].cap << endl;
}
}*/
Dinic dn(g);
int res = dn.solve(2 * M, 2 * M + 1);
cout << res << endl;
}