QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#30455 | #3855. Regional development | whereismyteammate# | RE | 0ms | 0kb | C++20 | 1.3kb | 2022-04-28 20:24:39 | 2022-04-28 20:24:41 |
Judging History
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;
}
詳細信息
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