QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#30455#3855. Regional developmentwhereismyteammate#RE 0ms0kbC++201.3kb2022-04-28 20:24:392022-04-28 20:24:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-28 20:24:41]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2022-04-28 20:24:39]
  • 提交

answer

#include <bits/stdc++.h>

const int N = 1005;

int n, m, p, pre[N];
int a[N], b[N], c[N], out[N];
std::vector<int> G[N];

int dfs(int x) {
	if (out[x] > 0)
		return x;
	for (int e_id : G[x]) {
		int end_point = (c[e_id] > 0 ? a[e_id] : b[e_id]);
		if (end_point == x || pre[end_point]) {
			continue;
		}
		pre[end_point] = e_id;
		if (int t = dfs(end_point); t != -1)
			return t;
	}
	return -1;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> n >> m >> p;
	for (int i = 1; i <= m; ++i) {
		std::cin >> a[i] >> b[i] >> c[i];
		G[a[i]].push_back(i);
		G[b[i]].push_back(i);
		out[a[i]] += c[i];
		out[b[i]] -= c[i];
	}
	auto assign = [&](int e, int v) {
		out[a[e]] -= c[e];
		out[b[e]] += c[e];
		c[e] = v;
		out[a[e]] += c[e];
		out[b[e]] -= c[e];
	};
	for (int x = 1; x <= n; ++x) if (out[x] < 0) {
		memset(pre, 0, sizeof pre);
		int y = dfs(x);
		assert(y != -1);
		while (pre[y]) {
			int e = pre[y];
			if (a[e] == y) {
				assert(c[e] > 0);
				assign(e, c[e] - p);
				y = b[e];
			}
			else {
				assert(b[e] == y);
				assert(c[e] < 0);
				assign(e, c[e] + p);
				y = a[e];
			}
		}
		assert(out[x] >= 0);
	}
	for (int i = 1; i <= m; ++i)
		printf("%d\n", c[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

10 23 3
2 10 1
2 6 1
6 9 1
7 9 1
6 7 1
3 6 1
1 3 1
1 6 2
6 10 1
2 9 1
4 9 2
4 7 2
3 10 2
3 9 1
6 8 1
7 8 2
3 5 1
5 9 1
8 9 2
3 8 2
1 5 2
1 4 1
5 10 2

output:


result: