結果
問題 | No.654 Air E869120 |
ユーザー | akakimidori |
提出日時 | 2019-03-23 19:51:40 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 4,238 bytes |
コンパイル時間 | 876 ms |
コンパイル使用メモリ | 31,760 KB |
実行使用メモリ | 4,368 KB |
最終ジャッジ日時 | 2023-10-24 22:41:36 |
合計ジャッジ時間 | 2,611 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,368 KB |
testcase_01 | AC | 1 ms
4,368 KB |
testcase_02 | AC | 1 ms
4,368 KB |
testcase_03 | AC | 1 ms
4,368 KB |
testcase_04 | AC | 1 ms
4,368 KB |
testcase_05 | AC | 1 ms
4,368 KB |
testcase_06 | AC | 1 ms
4,368 KB |
testcase_07 | AC | 1 ms
4,368 KB |
testcase_08 | AC | 1 ms
4,368 KB |
testcase_09 | AC | 1 ms
4,368 KB |
testcase_10 | AC | 8 ms
4,368 KB |
testcase_11 | AC | 6 ms
4,368 KB |
testcase_12 | AC | 6 ms
4,368 KB |
testcase_13 | AC | 6 ms
4,368 KB |
testcase_14 | AC | 6 ms
4,368 KB |
testcase_15 | AC | 7 ms
4,368 KB |
testcase_16 | AC | 4 ms
4,368 KB |
testcase_17 | AC | 4 ms
4,368 KB |
testcase_18 | AC | 4 ms
4,368 KB |
testcase_19 | AC | 4 ms
4,368 KB |
testcase_20 | AC | 3 ms
4,368 KB |
testcase_21 | AC | 3 ms
4,368 KB |
testcase_22 | AC | 3 ms
4,368 KB |
testcase_23 | AC | 3 ms
4,368 KB |
testcase_24 | AC | 4 ms
4,368 KB |
testcase_25 | AC | 3 ms
4,368 KB |
testcase_26 | AC | 3 ms
4,368 KB |
testcase_27 | AC | 3 ms
4,368 KB |
testcase_28 | AC | 3 ms
4,368 KB |
testcase_29 | AC | 3 ms
4,368 KB |
testcase_30 | AC | 2 ms
4,368 KB |
testcase_31 | AC | 2 ms
4,368 KB |
testcase_32 | AC | 2 ms
4,368 KB |
testcase_33 | AC | 2 ms
4,368 KB |
testcase_34 | AC | 2 ms
4,368 KB |
testcase_35 | AC | 1 ms
4,368 KB |
testcase_36 | AC | 1 ms
4,368 KB |
testcase_37 | AC | 1 ms
4,368 KB |
testcase_38 | AC | 1 ms
4,368 KB |
testcase_39 | AC | 1 ms
4,368 KB |
ソースコード
#include<stdio.h> #include<stdlib.h> #include<stdint.h> #include<inttypes.h> #include<string.h> typedef int64_t flow_type; const flow_type flow_inf = (int64_t) 1000000000 * 1000; typedef struct flow_edge { int32_t vertex; int32_t next; flow_type capacity; } flow_edge; typedef struct maxFlowGraph { flow_edge *edge; int32_t *start; int32_t vertex_num; int32_t pointer; int32_t edge_length; } graph; graph* new_graph (const int32_t vertex_num) { graph *g = (graph *) calloc (1, sizeof (graph)); g->vertex_num = vertex_num; const int32_t initial_length = 4; g->edge = (flow_edge *) calloc (initial_length, sizeof (flow_edge)); g->start = (int32_t *) calloc (vertex_num, sizeof (int32_t)); g->pointer = 0; g->edge_length = initial_length; for (int32_t i = 0; i < vertex_num; ++i) { g->start[i] = -1; } return g; } void free_graph (graph * const g) { free (g->edge); free (g->start); free (g); } void clear_graph (graph * const g) { g->pointer = 0; memset (g->start, -1, sizeof (int32_t) * g->vertex_num); } void add_edge (graph * const g, const int32_t from, const int32_t to, const flow_type capa) { if (g->pointer == g->edge_length) { g->edge_length *= 2; g->edge = (flow_edge *) realloc (g->edge, sizeof (flow_edge) * g->edge_length); } const int32_t p = g->pointer; g->edge[p] = (flow_edge) {to, g->start[from], capa}; g->start[from] = p; g->edge[p + 1] = (flow_edge) {from, g->start[to], 0}; g->start[to] = p + 1; g->pointer += 2; } flow_type dinic_dfs (const int32_t v, graph * const g, const int32_t dst, const int32_t * const level, int32_t * const iter, flow_type e) { if (v == dst) return e; flow_type sum = 0; for (int32_t p = iter[v]; p != -1; p = g->edge[p].next, iter[v] = p) { const int32_t u = g->edge[p].vertex; const flow_type capa = g->edge[p].capacity; if (level[u] <= level[v] || capa <= 0) continue; const flow_type f = dinic_dfs (u, g, dst, level, iter, capa < e ? capa : e); if (f > 0) { g->edge[p].capacity -= f; g->edge[p ^ 1].capacity += f; sum += f; e -= f; if (e <= 0) return sum; } } return sum; } flow_type dinic (graph * const g, const int32_t src, const int32_t dst) { const int32_t vertex_num = g->vertex_num; int32_t * const level = (int32_t *) calloc (vertex_num, sizeof (int32_t)); int32_t * const queue = (int32_t *) calloc (vertex_num, sizeof (int32_t)); int32_t * const iter = (int32_t *) calloc (vertex_num, sizeof (int32_t)); flow_type flow = 0; while (1) { memset (level, 0, sizeof (int32_t) * vertex_num); int32_t front = 0; int32_t last = 0; level[dst] = vertex_num; queue[last++] = dst; while (front < last && level[src] == 0) { const int32_t v = queue[front++]; for (int32_t p = g->start[v]; p!=-1; p = g->edge[p].next) { const int32_t u = g->edge[p].vertex; if (g->edge[p ^ 1].capacity > 0 && level[u] == 0) { level[u] = level[v] - 1; queue[last++] = u; } } } if (level[src] == 0) break; memcpy (iter, g->start, sizeof (int32_t) * vertex_num); while (1) { flow_type f = dinic_dfs (src, g, dst, level, iter, flow_inf); if (f <= 0) break; flow += f; } } free (level); free (queue); free (iter); return flow; } typedef int32_t i32; typedef int64_t i64; void run(void){ i32 n, m, d; scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32, &n, &m, &d); i32 *u = (i32 *) calloc (5 * m, sizeof (i32)); i32 *v = u + m; i32 *p = v + m; i32 *q = p + m; i32 *w = q + m; for (i32 i = 0; i < m; ++i) { for (i32 j = i; j < 5 * m; j += m) { scanf("%" SCNi32, u + j); } } graph *g = new_graph (2 * m + 2); const i32 src = 2 * m; const i32 dst = 2 * m + 1; for (i32 i = 0; i < m; ++i) { if (u[i] == 1) { add_edge (g, src, i, flow_inf); } if (v[i] == n) { add_edge (g, i + m, dst, flow_inf); } add_edge (g, i, i + m, w[i]); for (i32 j = 0; j < m; ++j) { if (v[i] == u[j] && q[i] + d <= p[j]) { add_edge (g, i + m, j, flow_inf); } } } i64 ans = dinic (g, src, dst); printf("%" PRIi64 "\n", ans); } int main(void){ run(); return 0; }