結果
| 問題 | No.1615 Double Down |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2021-06-20 20:29:34 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 1,386 ms / 10,000 ms |
| コード長 | 5,777 bytes |
| コンパイル時間 | 423 ms |
| コンパイル使用メモリ | 35,456 KB |
| 実行使用メモリ | 21,584 KB |
| 最終ジャッジ日時 | 2024-07-17 15:16:57 |
| 合計ジャッジ時間 | 18,738 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 54 |
ソースコード
#include <stdio.h>#include <stdlib.h>typedef struct {int id, head, tail, flow, cap, cost;} edge;typedef struct List {struct List *next;edge *e;} list;const int sup = 1 << 30;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; 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 solve(int N, int M, int K, int L, int X[], int Y[], int Z[]){int i, k, m = 0, F = 0, F_tmp, u, w, s = N + M + 1, t = N + M + 2, bit[31], flag[200003] = {}, tmp[200003], q[200003], head, tail;long long ans = 0;list *adj[200003] = {}, d[800001], *p, *pp;edge e[800001];for (i = 1, bit[0] = 1; i <= K; i++) bit[i] = bit[i-1] << 1;for (i = 1; i <= N; i++) {u = s;w = i;e[m].id = m;e[m].tail = u;e[m].head = w;e[m].flow = 0;e[m].cap = 1;e[m].cost = K;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].flow = 0;e[m].cap = 0;e[m].cost = K;d[m].e = &(e[m]);d[m].next = adj[w];adj[w] = &(d[m++]);}for (i = 1; i <= M; i++) {u = i + N;w = t;e[m].id = m;e[m].tail = u;e[m].head = w;e[m].flow = 0;e[m].cap = 1;e[m].cost = K;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].flow = 0;e[m].cap = 0;e[m].cost = K;d[m].e = &(e[m]);d[m].next = adj[w];adj[w] = &(d[m++]);}for (k = K; k >= 0; k--) {for (i = 1; i <= L; i++) {u = X[i];w = Y[i] + N;if (Z[i] != k || flag[u] != 0 || flag[w] != 0) continue;e[m].id = m;e[m].tail = u;e[m].head = w;e[m].flow = 0;e[m].cap = 1;e[m].cost = k;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].flow = 0;e[m].cap = 0;e[m].cost = k;d[m].e = &(e[m]);d[m].next = adj[w];adj[w] = &(d[m++]);}F_tmp = Dinic(t, m, adj, e, s, t);ans += (long long)(F_tmp - F) * bit[k];F = F_tmp;for (u = 1; u <= t; u++) tmp[u] = 0;q[0] = s;tmp[s] = 1;for (head = 0, tail = 1; head < tail; head++) {u = q[head];for (pp = adj[u]; pp != NULL; pp = pp->next) {if (pp->e->flow == pp->e->cap || pp->e->head >= s) continue;w = pp->e->head;if (tmp[w] == 0) {tmp[w] = -tmp[u];q[tail++] = w;}}}q[0] = t;tmp[t] = 1;for (head = 0, tail = 1; head < tail; head++) {u = q[head];for (pp = adj[u]; pp != NULL; pp = pp->next) {if (e[pp->e->id ^ 1].flow == e[pp->e->id ^ 1].cap || pp->e->head >= s) continue;w = pp->e->head;if (tmp[w] == 0) {tmp[w] = -tmp[u];q[tail++] = w;}}}for (i = 0; i < m; i += 2) {u = e[i].tail;w = e[i].head;if (e[i].cap == 0 && e[i^1].cap == 0) continue;if (u == s) {if (tmp[w] == 0) {e[i].cap = 0;if (e[i].flow != 0) F--;} else e[i].cap = 1;} else if (w == t) {if (tmp[u] == 0) e[i].cap = 0;else e[i].cap = 1;} else {if (tmp[u] == 0 || tmp[w] == 0 || tmp[u] + tmp[w] == 2) e[i].cap = 0;else e[i].cap = 1;}e[i].flow = 0;e[i^1].cap = 0;}for (u = 1; u <= N + M; u++) if (flag[u] == 0 && tmp[u] >= 0) flag[u] = k;}return ans;}int main(){int i, j, N, M, K, L, r, X[200001], Y[200001], Z[200001];scanf("%d %d %d %d", &N, &M, &K, &L);for (i = 1; i <= L; i++) scanf("%d %d %d", &(X[i]), &(Y[i]), &(Z[i]));printf("%lld\n", solve(N, M, K, L, X, Y, Z));fflush(stdout);return 0;}