QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#666603#7737. Extending Distance369PaiWA 3ms10260kbC++145.3kb2024-10-22 19:17:082024-10-22 19:17:11

Judging History

你现在查看的是最新测评结果

  • [2024-10-22 19:17:11]
  • 评测
  • 测评结果：WA
  • 用时：3ms
  • 内存：10260kb
查看
  • [2024-10-22 19:17:08]
  • 提交

answer

#include <bits/stdc++.h>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

struct PrimalDual {
	int n, s, t;
	struct graph {
		int tot, hd[605];
		int nxt[10005], to[10005], flw[10005], cst[10005];

		void clear(int n) {tot = 1; memset(hd, 0, sizeof(int) * n); return;}
		void add(int u, int v, int f, int c) {
			nxt[++tot] = hd[u];
			hd[u] = tot;
			to[tot] = v;
			flw[tot] = f;
			cst[tot] = c;
			return;
		}
	} g;
	long long h[605], dis[605];
	int f[605], pre[605];
	struct node {
		int id;
		long long val;

		node() = default;
		node(int _id, long long _val): id(_id), val(_val) {}
		bool operator<(const node &b) const {return val > b.val;}
	};

	void clear(int n) {g.clear(n); return;}
	void add_edge(int u, int v, int f, int c) {g.add(u, v, f, c), g.add(v, u, 0, -c); return;}
	void spfa() {
		queue<int> q;
		memset(h, 0x3f, sizeof(h));
		h[s] = 0;
		q.push(s);
		while (!q.empty()) {
			int now = q.front();
			q.pop();
			f[now] = 0;
			for (int i = g.hd[now]; i; i = g.nxt[i])
				if (g.flw[i] && h[g.to[i]] > h[now] + g.cst[i]) {
					h[g.to[i]] = h[now] + g.cst[i];
					if (!f[g.to[i]]) q.push(g.to[i]), f[g.to[i]] = 1;
				}
		}
		return;
	}
	int dijkstra() {
		priority_queue<node> q;
		memset(dis, 0x3f, sizeof(dis));
		memset(pre, 0, sizeof(pre));
		q.emplace(s, dis[s] = 0);
		while (!q.empty()) {
			int now = q.top().id;
			long long tmp = q.top(). val;
			q.pop();
			if (dis[now] != tmp) continue;
			for (int i = g.hd[now]; i; i = g.nxt[i])
				if (g.flw[i] && dis[g.to[i]] > dis[now] + g.cst[i] + h[now] - h[g.to[i]]) {
					q.emplace(g.to[i], dis[g.to[i]] = dis[now] + g.cst[i] + h[now] - h[g.to[i]]);
					pre[g.to[i]] = i ^ 1;
				}
		}
		return pre[t];
	}
	long long solve(int lim) {
		long long ans = 0;
		int flow = 0;
		spfa();
		while (flow < lim && dijkstra()) {
			for (int i = 1; i <= n; i++)
				if (dis[i] < 0x3f3f3f3f3f3f3f3f) h[i] += dis[i];
			int mnflow = 0x3f3f3f3f;
			for (int i = t; i != s; i = g.to[pre[i]]) mnflow = min(mnflow, g.flw[pre[i] ^ 1]);
			mnflow = min(mnflow, lim - flow);
			for (int i = t; i != s; i = g.to[pre[i]]) g.flw[pre[i] ^ 1] -= mnflow, g.flw[pre[i]] += mnflow;
			// eprintf("%d %lld\n", mnflow, h[t]);
			ans += mnflow * h[t];
			flow += mnflow;
		}
		return ans;
	}
} F;

int T, n, m, k;
long long r[505][505], c[505][505];
int idr1[505][505], idr2[505][505], idc1[505][505], idc2[505][505];
struct graph {
	int tot, hd[605];
	int nxt[10005], to[10005], dt[10005];

	void clear(int n) {tot = 0; memset(hd, 0, sizeof(int) * n); return;}
	void add(int u, int v, int w) {
		nxt[++tot] = hd[u];
		hd[u] = tot;
		to[tot] = v;
		dt[tot] = w;
		return;
	}
} g;
long long dis[605];
struct node {
	int id;
	long long val;

	node() = default;
	node(int _id, long long _val): id(_id), val(_val) {}
	bool operator<(const node &b) const {return val > b.val;}
};

int getid(int x, int y) {return (x - 1) * m + y;}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &n, &m, &k);
		F.clear(n * m + 7);
		F.s = n * m + 1, F.t = n * m + 2, F.n = n * m + 2;
		int S = F.s, T = F.t;
		g.clear(n * m + 7);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j < m; j++) {
				scanf("%lld", &r[i][j]);
				int u = i == 1 ? F.s : getid(i - 1, j), v = i == n ? F.t : getid(i, j);
				g.add(getid(i, j), getid(i, j + 1), r[i][j]);
				g.add(getid(i, j + 1), getid(i, j), r[i][j]);
				F.add_edge(u, v, r[i][j], 0);
				F.add_edge(v, u, r[i][j], 0);
				idr1[i][j] = F.g.tot + 1;
				F.add_edge(u, v, 0x3f3f3f3f, 1);
				idr2[i][j] = F.g.tot + 1;
				F.add_edge(v, u, 0x3f3f3f3f, 1);
			}
		for (int i = 1; i < n; i++)
			for (int j = 1; j <= m; j++) {
				scanf("%lld", &c[i][j]);
				if (j == 1 || j == m) continue;
				int u = getid(i, j - 1), v = getid(i, j);
				g.add(getid(i, j), getid(i + 1, j), c[i][j]);
				g.add(getid(i + 1, j), getid(i, j), c[i][j]);
				F.add_edge(u, v, c[i][j], 0);
				F.add_edge(v, u, c[i][j], 0);
				idc1[i][j] = F.g.tot + 1;
				F.add_edge(u, v, 0x3f3f3f3f, 1);
				idc2[i][j] = F.g.tot + 1;
				F.add_edge(v, u, 0x3f3f3f3f, 1);
			}
		for (int i = 1; i <= n; i++) g.add(S, getid(i, 1), 0), g.add(getid(i, m), T, 0);
		priority_queue<node> q;
		memset(dis, 0x3f, sizeof(dis));
		q.emplace(S, dis[S] = 0);
		while (!q.empty()) {
			int now = q.top().id;
			long long tmp = q.top(). val;
			q.pop();
			if (dis[now] != tmp) continue;
			for (int i = g.hd[now]; i; i = g.nxt[i])
				if (dis[g.to[i]] > dis[now] + g.dt[i])
					q.emplace(g.to[i], dis[g.to[i]] = dis[now] + g.dt[i]);
		}
		eprintf("shortest path: %lld\n", dis[T]);
		long long ans = F.solve(dis[T] + k);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j < m; j++) r[i][j] += F.g.flw[idr1[i][j] ^ 1] + F.g.flw[idr2[i][j] ^ 1];
		for (int i = 1; i < n; i++)
			for (int j = 2; j < m; j++) c[i][j] += F.g.flw[idc1[i][j] ^ 1] + F.g.flw[idc2[i][j] ^ 1];
		printf("%lld\n", ans);
		for (int i = 1; i <= n; i++, puts(""))
			for (int j = 1; j < m; j++) printf("%lld ", r[i][j]);
		for (int i = 1; i < n; i++, puts(""))
			for (int j = 1; j <= m; j++) printf("%lld ", c[i][j]);
	}
	return 0;
}
/*
2
3 4 6
4 2 15 
7 1 11 
13 4 5 
3 6 1 2 
5 2 15 3 
3 3 3
2 3 
2 3 
3 3 
1 1 1 
2 2 2 

*/
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 9980kb

input:

2
3 4 6
2 1 15
7 1 9
13 3 2
3 6 1 2
5 2 15 3
3 3 3
1 1
2 2
3 3
1 1 1
2 2 2

output:

9
4 2 15 
7 1 11 
13 4 5 
3 6 1 2 
5 2 15 3 
4
2 3 
2 3 
3 3 
1 1 1 
2 2 2

result:

ok Correct. (2 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 10260kb

input:

125
4 4 48
33 9 39
38 74 3
18 44 9
20 91 19
76 95 17 16
61 88 50 49
68 18 33 84
4 4 14
54 69 42
47 90 28
2 73 59
1 20 90
43 22 74 19
27 67 46 43
42 21 78 80
4 4 93
12 67 38
13 85 39
74 68 77
71 80 64
92 97 53 46
66 6 30 20
66 70 71 24
4 4 34
43 86 55
49 34 73
78 77 90
99 49 5
55 4 63 47
80 24 15 3
8...

output:

87
35 36 39 
38 74 22 
20 68 22 
20 91 19 
76 95 17 16 
61 88 50 49 
68 18 33 84 
14
54 69 42 
47 90 28 
2 73 59 
2 33 90 
43 22 74 19 
27 67 46 43 
42 21 78 80 
166
71 85 54 
71 85 54 
74 68 77 
71 80 64 
92 97 53 46 
66 6 30 20 
66 70 71 24 
34
45 86 55 
49 34 73 
78 77 90 
99 49 37 
55 4 63 47 
8...

result:

ok Correct. (125 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 9980kb

input:

80
5 5 97
10 18 14 13
17 15 16 11
15 10 14 15
12 17 12 15
12 11 15 15
19 19 13 19 19
19 17 10 10 19
12 13 18 11 20
12 17 14 13 12
5 5 65
13 15 13 20
18 19 13 20
10 19 18 17
19 19 11 14
12 18 11 10
18 14 18 19 18
20 11 17 11 17
16 13 19 18 13
16 14 17 11 18
5 5 3
15 10 10 18
17 17 17 14
13 15 15 19
1...

output:

473
12 20 14 104 
17 15 16 102 
17 12 15 106 
14 17 13 106 
14 14 16 106 
19 19 13 19 19 
19 17 10 10 19 
12 13 18 11 20 
12 17 14 13 12 
271
18 18 13 67 
18 19 13 66 
15 20 18 63 
24 20 11 61 
24 20 11 61 
18 14 18 19 18 
20 11 17 11 17 
16 13 19 18 13 
16 14 17 11 18 
3
15 13 10 18 
17 17 17 14 
1...

result:

ok Correct. (80 test cases)

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 10012kb

input:

55
6 6 98
943830625 154853276 396311720 585129723 216006508
789713291 522861691 174874210 616414184 931597164
831871942 149821142 520941619 814161584 200419736
646044877 574761262 188910317 673355715 723256093
264106685 163628126 318085983 226850181 101764170
179381345 486537031 346100002 805792579 ...

output:

98
943830625 154853276 396311720 585129723 216006508 
789713291 522861691 174874210 616414184 931597164 
831871942 149821142 520941619 814161584 200419736 
646044877 574761262 188910317 673355715 723256093 
264106685 163628224 318085983 226850181 101764170 
179381345 486537031 346100002 805792579 50...

result:

wrong answer The length of shortest path shoult extend exactly K. (test case 4)
English 繁體中文 简体中文

服务器时间: 2024-12-05 08:25:56 | 开源项目