結果
| 問題 | No.1615 Double Down |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2021-05-23 01:02:19 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,037 bytes |
| コンパイル時間 | 457 ms |
| コンパイル使用メモリ | 36,012 KB |
| 実行使用メモリ | 10,348 KB |
| 最終ジャッジ日時 | 2024-07-17 15:10:23 |
| 合計ジャッジ時間 | 39,687 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 WA * 30 |
ソースコード
#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 int sup_int = 1 << 30;const long long sup = 1LL << 60, inf = -(1LL << 60);void chmin(int* a, int b){if (*a > b) *a = b;}int DFS(list *aux[], edge f[], int par[], int u){int i, w, c, argmin;for (; aux[u] != NULL; aux[u] = aux[u]->next) {if (aux[u]->e->flow == aux[u]->e->cap) continue;w = aux[u]->e->head;if (par[w] == -3) {for (i = aux[u]->e->id, c = sup_int; par[w] != -2; i = par[w]) {chmin(&c, f[i].cap - f[i].flow);w = f[i].tail;if (f[i].cap - f[i].flow == c) argmin = w;}for (i = aux[u]->e->id, w = aux[u]->e->head; par[w] != -2; i = par[w]) {f[i].flow += c;w = f[i].tail;}if (argmin != u) {par[u] = -1;return argmin;}} else if (par[w] == -1) {par[w] = aux[u]->e->id;w = DFS(aux, f, par, w);if (w > 0 && w != u) {par[u] = -1;return w;}}}return 0;}int Dinic(int N, int M, list* adj[], edge e[], int s, int t){int i, u, w, ans = 0, add, *par = (int*)malloc(sizeof(int) * (N + 1)), *dist = (int*)malloc(sizeof(int) * (N + 1)), *q = (int*)malloc(sizeof(int)* (N + 1)), head, tail;list **aux = (list**)malloc(sizeof(list*) * (N + 1)), *df = (list*)malloc(sizeof(list) * (M + 1)), *p;edge *f = (edge*)malloc(sizeof(edge) * (M + 1));for (i = 0; i < M; i++) f[i].flow = 0;do {for (u = 1; u <= N; u++) {dist[u] = -1;aux[u] = NULL;}dist[s] = 0;q[0] = s;for (head = 0, tail = 1; head < tail; head++) {u = q[head];for (p = adj[u]; p != NULL; p = p->next) {if (p->e->flow == p->e->cap) continue;w = p->e->head;if (dist[w] == -1) {dist[w] = dist[u] + 1;q[tail++] = w;}if (dist[w] == dist[u] + 1) {i = p->e->id;f[i].id = i;f[i].tail = u;f[i].head = w;f[i].flow = 0;f[i].cap = p->e->cap - p->e->flow;df[i].e = &(f[i]);df[i].next = aux[u];aux[u] = &(df[i]);}}}for (u = 1; u <= N; u++) par[u] = -1;par[s] = -2;par[t] = -3;DFS(aux, f, par, s);for (i = 0, add = 0; i < M; i++) {if (e[i].flow == e[i].cap || dist[e[i].head] != dist[e[i].tail] + 1 || f[i].flow == 0) continue;if (f[i].tail == s) add += f[i].flow;if (e[i^1].flow > 0) {e[i^1].flow -= f[i].flow;e[i].cap -= f[i].flow;} else {e[i].flow += f[i].flow;e[i^1].cap += f[i].flow;}}ans += add;} while (add != 0);free(par);free(dist);free(q);free(aux);free(df);free(f);return ans;}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, tmp = 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 = 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;}tmp += (long long)e[i].cost * min;}if (ans > tmp) ans = tmp;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;}long long solve_by_MCF(int N, int M, int K, int L, int X[], int Y[], int Z[]){int i, k = 0, u, w, s = N + M + 1, t = N + M + 2, bit[31];list *adj[10003] = {}, d[220001], *p;edge e[220001];for (i = 1, bit[0] = 1; i <= K; i++) bit[i] = bit[i-1] << 1;for (i = 1; i <= L; i++) {u = X[i];w = Y[i] + N;e[k].id = k;e[k].tail = u;e[k].head = w;e[k].flow = 0;e[k].cap = 1;e[k].cost = -bit[Z[i]];d[k].e = &(e[k]);d[k].next = adj[u];adj[u] = &(d[k++]);e[k].id = k;e[k].tail = w;e[k].head = u;e[k].flow = 0;e[k].cap = 0;e[k].cost = bit[Z[i]];d[k].e = &(e[k]);d[k].next = adj[w];adj[w] = &(d[k++]);}for (i = 1; i <= N; i++) {u = s;w = i;e[k].id = k;e[k].tail = u;e[k].head = w;e[k].flow = 0;e[k].cap = 1;e[k].cost = 0;d[k].e = &(e[k]);d[k].next = adj[u];adj[u] = &(d[k++]);e[k].id = k;e[k].tail = w;e[k].head = u;e[k].flow = 0;e[k].cap = 0;e[k].cost = 0;d[k].e = &(e[k]);d[k].next = adj[w];adj[w] = &(d[k++]);}for (i = 1; i <= M; i++) {u = i + N;w = t;e[k].id = k;e[k].tail = u;e[k].head = w;e[k].flow = 0;e[k].cap = 1;e[k].cost = 0;d[k].e = &(e[k]);d[k].next = adj[u];adj[u] = &(d[k++]);e[k].id = k;e[k].tail = w;e[k].head = u;e[k].flow = 0;e[k].cap = 0;e[k].cost = 0;d[k].e = &(e[k]);d[k].next = adj[w];adj[w] = &(d[k++]);}int b[10003] = {};b[t] = Dinic(t, k, adj, e, s, t);b[s] = -b[t];for (i = 0; i < k; i += 2) {e[i].flow = 0;e[i].cap = 1;e[i^1].flow = 0;e[i^1].cap = 0;}return -succesive_shortest_path(t, k, adj, e, b);}int main(){int i, j, N, M, K, L, r, X[100001], Y[100001], Z[100001];scanf("%d %d %d %d", &N, &M, &K, &L);if (N + M >= 10000) return 0;for (i = 1; i <= L; i++) scanf("%d %d %d", &(X[i]), &(Y[i]), &(Z[i]));printf("%lld\n", solve_by_MCF(N, M, K, L, X, Y, Z));fflush(stdout);return 0;}