#238526 (C++11(old_compat)) No.654 Air E869120

• 問題: No.654 Air E869120
• ユーザー: ats5515
• 提出日時: 2018-02-23 23:47:00
• 言語: C++11(old_compat) (gcc 12.4.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 43 ms / 2,000 ms
• コード長: 3,983 bytes
• コンパイル時間: 2,165 ms
• コンパイル使用メモリ: 192,604 KB
• 実行使用メモリ: 66,944 KB
• 最終ジャッジ日時: 2026-03-08 16:16:06
• 合計ジャッジ時間: 3,935 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

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

ソースコード

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