結果
| 問題 | No.1678 Coin Trade (Multiple) |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2021-09-10 23:12:52 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 912 ms / 5,000 ms |
| コード長 | 4,944 bytes |
| コンパイル時間 | 1,164 ms |
| コンパイル使用メモリ | 33,680 KB |
| 実行使用メモリ | 10,368 KB |
| 最終ジャッジ日時 | 2024-06-12 03:44:20 |
| 合計ジャッジ時間 | 14,971 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 56 |
ソースコード
#include <stdio.h>#include <stdlib.h>typedef struct {long long key;int id;} data;typedef struct {data *obj;int size;} min_heap;void push(data x, min_heap* h){int i = ++(h->size), j = i >> 1;data tmp;h->obj[i] = x;while (j > 0) {if (h->obj[i].key < h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;i = j;j >>= 1;} else break;}}data pop(min_heap* h){int i = 1, j = 2;data output = h->obj[1], tmp;h->obj[1] = h->obj[(h->size)--];while (j <= h->size) {if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1;if (h->obj[j].key < h->obj[i].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;i = j;j <<= 1;} else break;}return output;}typedef struct {int id, head, tail, flow, cap, cost;} edge;typedef struct List {struct List *next;edge *e;} list;const long long sup = (long long)1 << 60, inf = -sup;long long succesive_shortest_path(int N, int M, list* adj[], edge e[], int b[]){int i, j, k, u, w, *flag = (int*)malloc(sizeof(int) * (N + 1)), *def = (int*)malloc(sizeof(int) * (N + 1));long long ans = 0, *dist = (long long*)malloc(sizeof(long long) * (N + 1)), *pi = (long long*)malloc(sizeof(long long) * (N + 1));edge **prev = (edge**)malloc(sizeof(edge*) * (N + 1));list *p;data d;min_heap h_def, h_dist;h_def.size = 0;h_def.obj = (data*)malloc(sizeof(data) * (N + 1));h_dist.obj = (data*)malloc(sizeof(data) * (M * 2 + 1));for (i = 0; i < M; i++) ans += (long long)e[i].cost * e[i].flow;for (i = 1; i <= N; i++) pi[i] = sup;for (i = 1; i <= N; i++) {for (p = adj[i], def[i] = b[i]; p != NULL; p = p->next) def[i] += p->e->flow - e[(p->e->id)^1].flow;if (def[i] < 0) {d.key = def[i];d.id = i;push(d, &h_def);if (pi[i] == sup) {pi[i] = 0;for (j = 1; j <= N; j++) {for (k = 0, flag[0] = 0; k < M; k++) {if (e[k].flow == e[k].cap) continue;u = e[k].tail;w = e[k].head;if (pi[u] != sup && pi[w] > pi[u] + e[k].cost) {flag[0] = 1;pi[w] = pi[u] + e[k].cost;}}if (flag[0] == 0) break;}if (j > N) return inf;}}}int s, t, min;while (h_def.size > 0) {d = pop(&h_def);s = d.id;for (u = 1; u <= N; u++) {flag[u] = 0;dist[u] = sup;prev[u] = NULL;}dist[s] = 0;h_dist.size = 0;d.key = 0;d.id = s;push(d, &h_dist);while (h_dist.size > 0) {d = pop(&h_dist);u = d.id;if (flag[u] != 0) continue;else flag[u] = 1;for (p = adj[u]; p != NULL; p = p->next) {w = p->e->head;if (p->e->flow == p->e->cap) continue;else if (dist[w] > dist[u] + p->e->cost + pi[u] - pi[w]) {dist[w] = dist[u] + p->e->cost + pi[u] - pi[w];prev[w] = p->e;d.key = dist[w];d.id = w;push(d, &h_dist);}}}for (t = 1; t <= N; t++) if (dist[t] != sup && def[t] > 0) break;if (t > N) return sup;for (u = t, min = (-def[s] < def[t])? -def[s]: def[t]; prev[u] != NULL; u = prev[u]->tail) {if (min > prev[u]->cap - prev[u]->flow) min = prev[u]->cap - prev[u]->flow;}for (u = t; prev[u] != NULL; u = prev[u]->tail) {i = prev[u]->id;if (e[i^1].flow > 0) {e[i^1].flow -= min;e[i].cap -= min;} else {e[i].flow += min;e[i^1].cap += min;}ans += (long long)e[i].cost * min;}for (i = 1; i <= N; i++) if (dist[i] != sup) pi[i] += dist[i];def[s] += min;def[t] -= min;if (def[s] < 0) {d.key = def[s];d.id = s;push(d, &h_def);}}free(flag);free(dist);free(def);free(pi);free(prev);free(h_def.obj);free(h_dist.obj);return ans;}int main(){const long long sup = 1LL << 60, inf = -sup;int i, j, N, K, A[50001], M, B, u, w, m = 0;list *adj[50001] = {}, d[200000];edge e[200000];scanf("%d %d", &N, &K);for (i = 1; i < N; i++) {u = i;w = i + 1;e[m].id = m;e[m].tail = u;e[m].head = w;e[m].cap = K;e[m].flow = 0;e[m].cost = 0;d[m].e = &(e[m]);d[m].next = adj[u];adj[u] = &(d[m++]);e[m].id = m;e[m].tail = w;e[m].head = u;e[m].cap = 0;e[m].flow = 0;e[m].cost = 0;d[m].e = &(e[m]);d[m].next = adj[w];adj[w] = &(d[m++]);}for (i = 1; i <= N; i++) {scanf("%d %d", &(A[i]), &M);for (j = 1; j <= M; j++) {scanf("%d", &B);if (A[i] > A[B]) {u = B;w = i;e[m].id = m;e[m].tail = u;e[m].head = w;e[m].cap = 1;e[m].flow = 0;e[m].cost = A[B] - A[i];d[m].e = &(e[m]);d[m].next = adj[u];adj[u] = &(d[m++]);e[m].id = m;e[m].tail = w;e[m].head = u;e[m].cap = 0;e[m].flow = 0;e[m].cost = A[i] - A[B];d[m].e = &(e[m]);d[m].next = adj[w];adj[w] = &(d[m++]);}}}int b[50001] = {};b[1] = -K;b[N] = K;printf("%lld\n", -succesive_shortest_path(N, m, adj, e, b));fflush(stdout);return 0;}