結果
問題 | No.654 Air E869120 |
ユーザー | 加藤優佑 |
提出日時 | 2021-01-08 02:27:34 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 4,605 bytes |
コンパイル時間 | 324 ms |
コンパイル使用メモリ | 33,024 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-14 13:28:16 |
合計ジャッジ時間 | 1,722 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,824 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 1 ms
6,816 KB |
testcase_04 | AC | 1 ms
6,816 KB |
testcase_05 | AC | 1 ms
6,820 KB |
testcase_06 | AC | 1 ms
6,820 KB |
testcase_07 | AC | 1 ms
6,820 KB |
testcase_08 | AC | 1 ms
6,816 KB |
testcase_09 | AC | 1 ms
6,820 KB |
testcase_10 | AC | 7 ms
6,816 KB |
testcase_11 | AC | 6 ms
6,816 KB |
testcase_12 | AC | 6 ms
6,820 KB |
testcase_13 | AC | 6 ms
6,820 KB |
testcase_14 | AC | 6 ms
6,816 KB |
testcase_15 | AC | 6 ms
6,820 KB |
testcase_16 | AC | 7 ms
6,820 KB |
testcase_17 | AC | 9 ms
6,820 KB |
testcase_18 | AC | 7 ms
6,816 KB |
testcase_19 | AC | 7 ms
6,820 KB |
testcase_20 | AC | 4 ms
6,820 KB |
testcase_21 | AC | 4 ms
6,816 KB |
testcase_22 | AC | 2 ms
6,816 KB |
testcase_23 | AC | 3 ms
6,816 KB |
testcase_24 | AC | 4 ms
6,816 KB |
testcase_25 | AC | 2 ms
6,820 KB |
testcase_26 | AC | 2 ms
6,820 KB |
testcase_27 | AC | 2 ms
6,816 KB |
testcase_28 | AC | 3 ms
6,820 KB |
testcase_29 | AC | 2 ms
6,816 KB |
testcase_30 | AC | 2 ms
6,816 KB |
testcase_31 | AC | 2 ms
6,820 KB |
testcase_32 | AC | 2 ms
6,820 KB |
testcase_33 | AC | 2 ms
6,816 KB |
testcase_34 | AC | 2 ms
6,820 KB |
testcase_35 | AC | 1 ms
6,816 KB |
testcase_36 | AC | 1 ms
6,820 KB |
testcase_37 | AC | 1 ms
6,820 KB |
testcase_38 | AC | 1 ms
6,816 KB |
testcase_39 | AC | 1 ms
6,816 KB |
ソースコード
#include<stdio.h> #include<stdlib.h> #include<limits.h> #define MMAX 1000 #define MIN(a,b) ((a) < (b) ? (a) : (b)) typedef long long flow_type; struct flow_edge{ int vertex; int next; flow_type capacity; }; struct flow_graph{ struct flow_edge *edge; int *start; int vertex_num; int pointer; int edge_length; }; struct airline { int vertex; int ftime; }; struct flow_graph *graph; int *level; int Cmp_air(const void*, const void*); void Create_graph(int); void Insert_edge(int, int, flow_type); void Free_graph(void); int Bfs(int, int, int); flow_type Dfs(int, int, flow_type); int main(void) { int i, n, m, d, f[MMAX][5], alen = 1; flow_type maxflow = 0; struct airline a[2*MMAX+2]; scanf("%d %d %d", &n, &m, &d); for (i = 0; i < m; i++) { scanf("%d %d %d %d %d", &f[i][0], &f[i][1], &f[i][2], &f[i][3], &f[i][4]); f[i][3] += d; a[i*2].vertex = f[i][0]; a[i*2].ftime = f[i][2]; a[i*2+1].vertex = f[i][1]; a[i*2+1].ftime = f[i][3]; } a[m*2].vertex = 1; a[m*2].ftime = 0; a[m*2+1].vertex = n; a[m*2+1].ftime = 2000000000; qsort(a, 2 * m + 2, sizeof(struct airline), Cmp_air); for (i = 1; i < 2 * m + 2; i++) { if (Cmp_air(&a[alen-1], &a[i])) { a[alen].vertex = a[i].vertex; a[alen++].ftime = a[i].ftime; } } level = (int*)malloc(sizeof(int) * alen); Create_graph(alen); for (i = 0; i < m; i++) { int lo, hi, mid, uv[2]; struct airline ta; lo = 0; hi = alen - 1; ta.vertex = f[i][0]; ta.ftime = f[i][2]; while (lo <= hi) { mid = (lo + hi) / 2; if (Cmp_air(&a[mid], &ta) > 0) hi = mid - 1; else lo = mid + 1; } uv[0] = hi; lo = 0; hi = alen - 1; ta.vertex = f[i][1]; ta.ftime = f[i][3]; while (lo <= hi) { mid = (lo + hi) / 2; if (Cmp_air(&a[mid], &ta) > 0) hi = mid - 1; else lo = mid + 1; } uv[1] = hi; Insert_edge(uv[0], uv[1], f[i][4]); } for (i = 1; i < alen; i++) { if (a[i-1].vertex == a[i].vertex) Insert_edge(i - 1, i, __LONG_LONG_MAX__); } while (Bfs(0, alen - 1, alen)) maxflow += Dfs(0, alen - 1, __LONG_LONG_MAX__); printf("%lld\n", maxflow); Free_graph(); free(level); } int Cmp_air(const void *a, const void *b) { struct airline *ta = (struct airline*)a, *tb = (struct airline*)b; if (ta->vertex > tb->vertex) return 1; else if (ta->vertex < tb->vertex) return -1; else { if (ta->ftime > tb->ftime) return 1; else if (ta->ftime < tb->ftime) return -1; else return 0; } } void Create_graph(int vertex_num){ int i, initial_length = 2; graph = (struct flow_graph*)calloc(1, sizeof(struct flow_graph)); graph->vertex_num = vertex_num; graph->edge = (struct flow_edge*)calloc(initial_length, sizeof(struct flow_edge)); graph->start = (int*)calloc(vertex_num, sizeof(int)); graph->pointer = 0; graph->edge_length = initial_length; for(i = 0; i < vertex_num; i++) graph->start[i] = -1; } void Insert_edge(int from, int to, flow_type capa){ int p = graph->pointer; if(graph->pointer == graph->edge_length){ graph->edge_length *= 2; graph->edge = (struct flow_edge*)realloc(graph->edge, sizeof(struct flow_edge) * graph->edge_length); } graph->edge[p].vertex = to; graph->edge[p].next = graph->start[from]; graph->edge[p].capacity = capa; graph->start[from] = p; graph->edge[p+1].vertex = from; graph->edge[p+1].next = graph->start[to]; graph->edge[p+1].capacity = 0; graph->start[to] = p + 1; graph->pointer += 2; } void Free_graph(void) { free(graph->edge); free(graph->start); free(graph); } int Bfs(int s, int t, int size) { int i, p, head = 0, tail = 0, queue[size]; for (i = 0; i < size; i++) level[i] = -1; level[s] = 0; queue[tail++] = s; do { i = queue[head++]; for (p = graph->start[i]; p != -1; p = graph->edge[p].next) { int v = graph->edge[p].vertex; if (level[v] < 0 && graph->edge[p].capacity > 0) { queue[tail++] = v; level[v] = level[i] + 1; } } } while (head != tail); return level[t] >= 0; } flow_type Dfs(int u, int t, flow_type f) { int p; flow_type fsum = 0; if (u == t) return f; for (p = graph->start[u]; p != -1; p = graph->edge[p].next) { int v = graph->edge[p].vertex; if (level[u] < level[v] && graph->edge[p].capacity > 0) { flow_type ftemp = Dfs(v, t, MIN(f - fsum, graph->edge[p].capacity)); if (ftemp > 0) { graph->edge[p].capacity -= ftemp; graph->edge[p^1].capacity += ftemp; fsum += ftemp; if (fsum == f) break; } } } return fsum; }