結果
問題 | No.654 Air E869120 |
ユーザー | 加藤優佑 |
提出日時 | 2021-01-06 22:26:17 |
言語 | C (gcc 12.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,865 bytes |
コンパイル時間 | 435 ms |
コンパイル使用メモリ | 32,896 KB |
実行使用メモリ | 32,640 KB |
最終ジャッジ日時 | 2024-11-07 10:54:40 |
合計ジャッジ時間 | 2,228 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 1 ms
5,248 KB |
testcase_09 | AC | 1 ms
5,248 KB |
testcase_10 | AC | 8 ms
5,248 KB |
testcase_11 | AC | 7 ms
5,248 KB |
testcase_12 | AC | 7 ms
5,248 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 31 ms
32,384 KB |
testcase_17 | AC | 33 ms
32,512 KB |
testcase_18 | AC | 31 ms
32,640 KB |
testcase_19 | AC | 31 ms
32,512 KB |
testcase_20 | AC | 25 ms
32,384 KB |
testcase_21 | AC | 27 ms
32,256 KB |
testcase_22 | AC | 24 ms
32,256 KB |
testcase_23 | AC | 26 ms
32,256 KB |
testcase_24 | AC | 26 ms
32,256 KB |
testcase_25 | AC | 24 ms
32,256 KB |
testcase_26 | AC | 26 ms
32,384 KB |
testcase_27 | AC | 23 ms
32,384 KB |
testcase_28 | AC | 25 ms
32,384 KB |
testcase_29 | AC | 25 ms
32,384 KB |
testcase_30 | AC | 24 ms
32,128 KB |
testcase_31 | AC | 24 ms
32,256 KB |
testcase_32 | AC | 24 ms
32,128 KB |
testcase_33 | AC | 24 ms
32,256 KB |
testcase_34 | AC | 24 ms
32,128 KB |
testcase_35 | AC | 1 ms
5,248 KB |
testcase_36 | AC | 1 ms
5,248 KB |
testcase_37 | AC | 1 ms
5,248 KB |
testcase_38 | AC | 1 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
ソースコード
#include<stdio.h> #include<stdlib.h> #include<limits.h> #define MMAX 1000 #define MIN(a,b) ((a) < (b) ? (a) : (b)) struct node { int id; long long cap; struct node *next; }; struct airline { int vertex; int ftime; }; struct node **list; int *level, *queue; long long **flow; int cmp_air(const void*, const void*); void Insert(int, int, long long); int Bfs(int, int, int); long long Dfs(int, int, long long); int main(void) { int i, n, m, d, f[MMAX][5], alen = 1; long long 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 = 1000000000; 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; } } list = (struct node**)malloc(sizeof(struct node*) * alen); flow = (long long**)malloc(sizeof(long long*) * alen); level = (int*)malloc(sizeof(int) * alen); queue = (int*)malloc(sizeof(int) * alen); for (i = 0; i < alen; i++) { list[i] = NULL; flow[i] = (long long*)calloc(alen, sizeof(long)); } 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(uv[0], uv[1], f[i][4]); } for (i = 1; i < alen; i++) { if (a[i-1].vertex == a[i].vertex) Insert(i - 1, i, __LONG_LONG_MAX__); } while (Bfs(0, alen - 1, alen)) maxflow += Dfs(0, alen - 1, __LONG_LONG_MAX__); printf("%lld\n", maxflow); for (i = 0; i < alen; i++) { free(list[i]); free(flow[i]); } free(list); free(flow); free(level); free(queue); } 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 Insert(int a, int b, long long c) { struct node *p = (struct node*)malloc(sizeof(struct node)); p->id = b; p->cap = c; p->next = list[a]; list[a] = p; p = (struct node*)malloc(sizeof(struct node)); p->id = a; p->cap = 0; p->next = list[b]; list[b] = p; } int Bfs(int s, int t, int size) { struct node *n; int i, head = 0, tail = 0; for (i = 0; i < size; i++) level[i] = -1; level[s] = 0; queue[tail++] = s; do { i = queue[head++]; for (n = list[i]; n != NULL; n = n->next) { int v = n->id; if (level[v] < 0 && flow[i][v] < n->cap) { queue[tail++] = v; level[v] = level[i] + 1; } } } while (head != tail); return level[t] >= 0; } long long Dfs(int u, int t, long long f) { long long fsum = 0; struct node *n; if (u == t) return f; for (n = list[u]; n != NULL; n = n->next) { int v = n->id; if (level[u] < level[v] && flow[u][v] < n->cap) { long long ftemp = Dfs(v, t, MIN(f - fsum, n->cap - flow[u][v])); if (ftemp > 0) { flow[u][v] += ftemp; flow[v][u] -= ftemp; fsum += ftemp; if (fsum == f) break; } } } return fsum; }