結果

問題 No.1678 Coin Trade (Multiple)
ユーザー 👑 ygussanyygussany
提出日時 2021-09-10 23:12:52
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 1,043 ms / 5,000 ms
コード長 4,944 bytes
コンパイル時間 1,595 ms
コンパイル使用メモリ 33,228 KB
実行使用メモリ 12,764 KB
最終ジャッジ日時 2023-09-02 21:27:25
合計ジャッジ時間 17,189 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,536 KB
testcase_01 AC 1 ms
4,548 KB
testcase_02 AC 1 ms
4,564 KB
testcase_03 AC 73 ms
8,492 KB
testcase_04 AC 427 ms
10,100 KB
testcase_05 AC 184 ms
11,656 KB
testcase_06 AC 137 ms
11,204 KB
testcase_07 AC 323 ms
10,052 KB
testcase_08 AC 211 ms
11,644 KB
testcase_09 AC 206 ms
10,624 KB
testcase_10 AC 82 ms
5,132 KB
testcase_11 AC 306 ms
10,664 KB
testcase_12 AC 69 ms
8,288 KB
testcase_13 AC 621 ms
11,156 KB
testcase_14 AC 169 ms
9,572 KB
testcase_15 AC 200 ms
10,948 KB
testcase_16 AC 66 ms
9,260 KB
testcase_17 AC 200 ms
11,500 KB
testcase_18 AC 2 ms
4,452 KB
testcase_19 AC 2 ms
4,544 KB
testcase_20 AC 2 ms
4,448 KB
testcase_21 AC 2 ms
6,080 KB
testcase_22 AC 2 ms
4,492 KB
testcase_23 AC 2 ms
4,544 KB
testcase_24 AC 1 ms
4,424 KB
testcase_25 AC 1 ms
4,528 KB
testcase_26 AC 1 ms
4,564 KB
testcase_27 AC 2 ms
6,188 KB
testcase_28 AC 1 ms
4,448 KB
testcase_29 AC 2 ms
4,544 KB
testcase_30 AC 2 ms
4,564 KB
testcase_31 AC 1 ms
4,400 KB
testcase_32 AC 2 ms
4,548 KB
testcase_33 AC 2 ms
4,452 KB
testcase_34 AC 2 ms
4,468 KB
testcase_35 AC 2 ms
4,540 KB
testcase_36 AC 1 ms
4,460 KB
testcase_37 AC 2 ms
5,988 KB
testcase_38 AC 2 ms
4,456 KB
testcase_39 AC 2 ms
5,884 KB
testcase_40 AC 2 ms
4,372 KB
testcase_41 AC 2 ms
6,084 KB
testcase_42 AC 2 ms
4,544 KB
testcase_43 AC 2 ms
4,548 KB
testcase_44 AC 1 ms
4,468 KB
testcase_45 AC 2 ms
5,820 KB
testcase_46 AC 2 ms
4,520 KB
testcase_47 AC 2 ms
4,544 KB
testcase_48 AC 1,043 ms
12,764 KB
testcase_49 AC 983 ms
10,888 KB
testcase_50 AC 837 ms
10,936 KB
testcase_51 AC 895 ms
11,632 KB
testcase_52 AC 827 ms
11,308 KB
testcase_53 AC 829 ms
10,796 KB
testcase_54 AC 809 ms
10,928 KB
testcase_55 AC 860 ms
11,564 KB
testcase_56 AC 846 ms
11,104 KB
testcase_57 AC 794 ms
11,088 KB
testcase_58 AC 380 ms
10,840 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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