結果

問題 No.654 Air E869120
ユーザー ats5515ats5515
提出日時 2018-02-23 23:47:00
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,983 bytes
コンパイル時間 599 ms
コンパイル使用メモリ 90,628 KB
最終ジャッジ日時 2024-04-27 02:31:45
合計ジャッジ時間 973 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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

ソースコード

diff # 

#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;
}
0