#659978 (C) No.1615 Double Down

提出ソース

結果

問題	No.1615 Double Down
ユーザー	👑 ygussany
提出日時	2021-05-23 01:02:19
言語	C (gcc 12.3.0)
結果	WA
実行時間	-
コード長	8,037 bytes
コンパイル時間	447 ms
コンパイル使用メモリ	34,856 KB
実行使用メモリ	9,344 KB
最終ジャッジ日時	2023-09-24 14:29:23
合計ジャッジ時間	40,644 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	4,883 ms 6,300 KB
testcase_28	AC	4,898 ms 6,300 KB
testcase_29	AC	6,944 ms 9,344 KB
testcase_30	AC	6,967 ms 7,152 KB
testcase_31	AC	7,075 ms 9,336 KB
testcase_32	AC	7,099 ms 7,252 KB
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	AC	19 ms 4,380 KB
testcase_37	AC	19 ms 4,376 KB
testcase_38	AC	29 ms 4,380 KB
testcase_39	AC	30 ms 4,380 KB
testcase_40	AC	27 ms 4,376 KB
testcase_41	AC	27 ms 4,380 KB
testcase_42	AC	64 ms 4,464 KB
testcase_43	AC	64 ms 4,452 KB
testcase_44	AC	63 ms 4,384 KB
testcase_45	AC	1 ms 4,376 KB
testcase_46	AC	1 ms 4,380 KB
testcase_47	AC	1 ms 4,376 KB
testcase_48	AC	1 ms 4,380 KB
testcase_49	AC	1 ms 4,380 KB
testcase_50	AC	1 ms 4,376 KB
testcase_51	AC	1 ms 4,376 KB
testcase_52	AC	1 ms 4,376 KB
testcase_53	AC	1 ms 4,376 KB
testcase_54	AC	1 ms 4,376 KB
testcase_55	AC	1 ms 4,376 KB
testcase_56	AC	1 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード