結果
問題 | No.654 Air E869120 |
ユーザー | nebukuro09 |
提出日時 | 2018-02-23 23:48:23 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 200 ms / 2,000 ms |
コード長 | 2,366 bytes |
コンパイル時間 | 973 ms |
コンパイル使用メモリ | 106,932 KB |
実行使用メモリ | 13,160 KB |
最終ジャッジ日時 | 2023-09-03 18:49:29 |
合計ジャッジ時間 | 3,384 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,384 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,384 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,384 KB |
testcase_10 | AC | 200 ms
11,612 KB |
testcase_11 | AC | 95 ms
12,596 KB |
testcase_12 | AC | 125 ms
12,376 KB |
testcase_13 | AC | 136 ms
11,856 KB |
testcase_14 | AC | 50 ms
11,584 KB |
testcase_15 | AC | 74 ms
13,160 KB |
testcase_16 | AC | 20 ms
11,532 KB |
testcase_17 | AC | 21 ms
11,568 KB |
testcase_18 | AC | 19 ms
11,316 KB |
testcase_19 | AC | 23 ms
12,360 KB |
testcase_20 | AC | 13 ms
11,784 KB |
testcase_21 | AC | 13 ms
11,864 KB |
testcase_22 | AC | 12 ms
11,036 KB |
testcase_23 | AC | 12 ms
11,560 KB |
testcase_24 | AC | 12 ms
11,304 KB |
testcase_25 | AC | 12 ms
10,860 KB |
testcase_26 | AC | 11 ms
11,292 KB |
testcase_27 | AC | 11 ms
11,520 KB |
testcase_28 | AC | 12 ms
11,296 KB |
testcase_29 | AC | 10 ms
11,548 KB |
testcase_30 | AC | 9 ms
11,540 KB |
testcase_31 | AC | 9 ms
11,072 KB |
testcase_32 | AC | 10 ms
12,316 KB |
testcase_33 | AC | 9 ms
11,284 KB |
testcase_34 | AC | 9 ms
11,592 KB |
testcase_35 | AC | 1 ms
4,384 KB |
testcase_36 | AC | 1 ms
4,380 KB |
testcase_37 | AC | 1 ms
4,380 KB |
testcase_38 | AC | 1 ms
4,384 KB |
testcase_39 | AC | 1 ms
4,384 KB |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; alias Plane = Tuple!(int, "u", int, "v", int, "p", int, "q", int, "w"); immutable long INF = 1L << 59; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto D = s[2]; auto P = new Plane[](M); foreach (i; 0..M) { s = readln.split.map!(to!int); P[i] = Plane(s[0], s[1], s[2], s[3], s[4]); } int source = M; int sink = M + 1; auto ff = new FordFulkerson(M + 2, source, sink); foreach (i; 0..M) { if (P[i].u == 1) { ff.add_edge(source, i, P[i].w); } if (P[i].v == N) { ff.add_edge(i, sink, P[i].w); } } foreach (i; 0..M) { foreach (j; 0..M) { if (i == j) continue; if (P[i].v == P[j].u && P[j].p - P[i].q >= D) { ff.add_edge(i, j, min(P[i].w, P[j].w)); } } } ff.run.writeln; } class FordFulkerson { int N, source, sink; int[][] adj; long[][] flow; bool[] used; this(int n, int s, int t) { N = n; source = s; sink = t; assert (s >= 0 && s < N && t >= 0 && t < N); adj = new int[][](N); flow = new long[][](N, N); used = new bool[](N); } void add_edge(int from, int to, long cap) { adj[from] ~= to; adj[to] ~= from; flow[from][to] = cap; } long dfs(int v, long min_cap) { if (v == sink) return min_cap; if (used[v]) return 0; used[v] = true; foreach (to; adj[v]) { if (!used[to] && flow[v][to] > 0) { auto bottleneck = dfs(to, min(min_cap, flow[v][to])); if (bottleneck == 0) continue; flow[v][to] -= bottleneck; flow[to][v] += bottleneck; return bottleneck; } } return 0; } long run() { long ret = 0; while (true) { foreach (i; 0..N) used[i] = false; long f = dfs(source, long.max); if (f > 0) ret += f; else return ret; } } }