#698559 (C) No.1678 Coin Trade (Multiple)

提出ソース

結果

問題	No.1678 Coin Trade (Multiple)
ユーザー	ygussany
提出日時	2021-09-10 23:12:52
言語	C (gcc 12.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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	75 ms 6,144 KB
testcase_04	AC	389 ms 8,576 KB
testcase_05	AC	178 ms 9,856 KB
testcase_06	AC	137 ms 9,344 KB
testcase_07	AC	319 ms 6,656 KB
testcase_08	AC	219 ms 7,296 KB
testcase_09	AC	196 ms 9,984 KB
testcase_10	AC	85 ms 5,376 KB
testcase_11	AC	290 ms 8,192 KB
testcase_12	AC	71 ms 5,376 KB
testcase_13	AC	625 ms 9,600 KB
testcase_14	AC	170 ms 6,016 KB
testcase_15	AC	213 ms 8,064 KB
testcase_16	AC	69 ms 7,936 KB
testcase_17	AC	207 ms 10,112 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	1 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	1 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	1 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	1 ms 5,376 KB
testcase_30	AC	1 ms 5,376 KB
testcase_31	AC	1 ms 5,376 KB
testcase_32	AC	1 ms 5,376 KB
testcase_33	AC	1 ms 5,376 KB
testcase_34	AC	1 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	1 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	1 ms 5,376 KB
testcase_40	AC	1 ms 5,376 KB
testcase_41	AC	1 ms 5,376 KB
testcase_42	AC	1 ms 5,376 KB
testcase_43	AC	2 ms 5,376 KB
testcase_44	AC	2 ms 5,376 KB
testcase_45	AC	1 ms 5,376 KB
testcase_46	AC	1 ms 5,376 KB
testcase_47	AC	2 ms 5,376 KB
testcase_48	AC	874 ms 10,240 KB
testcase_49	AC	912 ms 10,240 KB
testcase_50	AC	854 ms 10,240 KB
testcase_51	AC	849 ms 10,368 KB
testcase_52	AC	845 ms 10,112 KB
testcase_53	AC	887 ms 10,240 KB
testcase_54	AC	876 ms 10,240 KB
testcase_55	AC	893 ms 10,240 KB
testcase_56	AC	888 ms 10,368 KB
testcase_57	AC	881 ms 10,240 KB
testcase_58	AC	387 ms 10,368 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 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;
}

yukicoder

結果

テストケース

ソースコード