QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#382375 | #602. 最小费用最大流(随机数据) | Isrothy | 100 ✓ | 145ms | 4388kb | C++23 | 3.7kb | 2024-04-08 13:15:33 | 2024-04-08 13:15:33 |
Judging History
answer
#include <cstdint>
#include <cstdio>
#include <queue>
#include <vector>
struct PrimalDual {
static constexpr int64_t INF = 0x3f3f3f3f3f3f3f3f;
struct Edge {
int from, to;
int64_t cap, cost, flow;
Edge(int from, int to, int64_t cap, int64_t cost)
: from(from), to(to), cap(cap), cost(cost), flow(0) {}
};
std::vector<Edge> edges;
std::vector<std::vector<int>> adj;
std::vector<int64_t> dis, h;
std::vector<bool> vis, in_queue;
int n;
explicit PrimalDual(int n) : adj(n), dis(n), h(n), vis(n), in_queue(n), n(n) {}
void add_edge(int u, int v, int64_t cap, int64_t cost) {
adj[u].push_back((int) edges.size());
edges.emplace_back(u, v, cap, cost);
adj[v].push_back((int) edges.size());
edges.emplace_back(v, u, 0, -cost);
}
void spfa(int t) {
std::queue<int> q;
std::vector<bool> in_queue(n, false);
std::fill(dis.begin(), dis.end(), INF);
dis[t] = 0;
in_queue[t] = true;
q.push(t);
while (!q.empty()) {
auto u = q.front();
q.pop();
in_queue[u] = false;
for (auto i: adj[u]) {
const auto &e = edges[i ^ 1];
if (e.flow != e.cap && dis[u] + e.cost < dis[e.from]) {
dis[e.from] = dis[u] + e.cost;
if (!in_queue[e.from]) {
in_queue[e.from] = true;
q.push(e.from);
}
}
}
}
}
void dijkstra(int t) {
std::priority_queue<std::pair<int, int>> q;
std::fill(dis.begin(), dis.end(), INF);
dis[t] = 0;
q.emplace(0, t);
while (!q.empty()) {
auto [d, u] = q.top();
q.pop();
if (dis[u] != -d) {
continue;
}
for (auto i: adj[u]) {
const auto &e = edges[i ^ 1];
auto c = dis[u] + e.cost + h[u] - h[e.from];
if (e.flow < e.cap && c < dis[e.from]) {
dis[e.from] = c;
q.emplace(-c, e.from);
}
}
}
}
auto dfs(int u, int t, int64_t a) {
if (u == t) {
return a;
}
vis[u] = true;
auto m = a;
for (auto i: adj[u]) {
auto &e = edges[i];
if (e.flow < e.cap && !vis[e.to] && h[e.to] == h[u] - e.cost) {
auto f = dfs(e.to, t, std::min(m, e.cap - e.flow));
e.flow += f;
edges[i ^ 1].flow -= f;
m -= f;
if (m == 0) {
break;
}
}
}
return a - m;
}
auto minimum_cost_flow(int s, int t) {
int64_t flow = 0, cost = 0;
for (spfa(t); dis[s] != INF; dijkstra(t)) {
for (int i = 0; i < n; ++i) {
h[i] += dis[i];
}
while (true) {
std::fill(vis.begin(), vis.end(), false);
if (auto f = dfs(s, t, INF)) {
flow += f;
cost += f * h[s];
} else {
break;
}
}
}
return std::make_pair(flow, cost);
}
};
int main() {
int n, m;
scanf("%u %u", &n, &m);
PrimalDual pd(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
int64_t c, d;
scanf("%u %u %llu %llu", &u, &v, &c, &d);
pd.add_edge(u, v, c, d);
}
auto ans = pd.minimum_cost_flow(1, n);
printf("%lld %lld\n", ans.first, ans.second);
return 0;
}
詳細信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 3868kb
input:
8 27 2 3 2147483647 100 1 3 1 100 2 4 2147483647 10 1 4 1 10 2 4 2147483647 10 1 4 1 10 2 8 3 0 3 5 2147483647 100 1 5 1 100 3 8 1 0 3 2 2147483647 0 4 5 2147483647 10 1 5 1 10 4 8 1 0 4 2 2147483647 0 5 6 2147483647 1 1 6 1 1 5 6 2147483647 1 1 6 1 1 5 7 2147483647 1 1 7 1 1 5 8 3 0 5 2 2147483647 ...
output:
8 243
result:
ok 2 number(s): "8 243"
Test #2:
score: 10
Accepted
time: 0ms
memory: 3720kb
input:
12 49 2 10 2147483647 5 1 10 1 5 2 5 2147483647 50 1 5 1 50 2 9 2147483647 8 1 9 1 8 2 8 2147483647 47 1 8 1 47 2 11 2147483647 17 1 11 1 17 2 12 5 0 3 12 0 0 3 2 2147483647 0 4 6 2147483647 18 1 6 1 18 4 11 2147483647 12 1 11 1 12 4 9 2147483647 14 1 9 1 14 4 12 3 0 4 2 2147483647 0 5 11 2147483647...
output:
15 436
result:
ok 2 number(s): "15 436"
Test #3:
score: 10
Accepted
time: 1ms
memory: 3804kb
input:
27 169 2 15 2147483647 24 1 15 1 24 2 19 2147483647 96 1 19 1 96 2 12 2147483647 49 1 12 1 49 2 13 2147483647 75 1 13 1 75 2 24 2147483647 2 1 24 1 2 2 27 5 0 3 27 0 0 3 2 2147483647 0 4 11 2147483647 99 1 11 1 99 4 3 2147483647 85 1 3 1 85 4 27 2 0 4 2 2147483647 0 5 27 0 0 5 2 2147483647 0 6 9 214...
output:
60 4338
result:
ok 2 number(s): "60 4338"
Test #4:
score: 10
Accepted
time: 7ms
memory: 3924kb
input:
77 2149 2 42 2147483647 33 1 42 1 33 2 68 2147483647 30 1 68 1 30 2 76 2147483647 13 1 76 1 13 2 51 2147483647 93 1 51 1 93 2 12 2147483647 39 1 12 1 39 2 57 2147483647 74 1 57 1 74 2 70 2147483647 21 1 70 1 21 2 73 2147483647 24 1 73 1 24 2 52 2147483647 54 1 52 1 54 2 15 2147483647 99 1 15 1 99 2 ...
output:
1000 74606
result:
ok 2 number(s): "1000 74606"
Test #5:
score: 10
Accepted
time: 21ms
memory: 3904kb
input:
102 4199 2 48 2147483647 42 1 48 1 42 2 85 2147483647 50 1 85 1 50 2 22 2147483647 83 1 22 1 83 2 95 2147483647 97 1 95 1 97 2 82 2147483647 34 1 82 1 34 2 25 2147483647 72 1 25 1 72 2 4 2147483647 17 1 4 1 17 2 47 2147483647 10 1 47 1 10 2 71 2147483647 12 1 71 1 12 2 68 2147483647 39 1 68 1 39 2 2...
output:
2000 161420
result:
ok 2 number(s): "2000 161420"
Test #6:
score: 10
Accepted
time: 19ms
memory: 3924kb
input:
102 4199 2 79 2147483647 13 1 79 1 13 2 83 2147483647 73 1 83 1 73 2 75 2147483647 90 1 75 1 90 2 30 2147483647 92 1 30 1 92 2 54 2147483647 25 1 54 1 25 2 66 2147483647 53 1 66 1 53 2 52 2147483647 37 1 52 1 37 2 63 2147483647 46 1 63 1 46 2 11 2147483647 20 1 11 1 20 2 55 2147483647 53 1 55 1 53 2...
output:
2000 143072
result:
ok 2 number(s): "2000 143072"
Test #7:
score: 10
Accepted
time: 14ms
memory: 3928kb
input:
102 4199 2 39 2147483647 45 1 39 1 45 2 51 2147483647 11 1 51 1 11 2 86 2147483647 63 1 86 1 63 2 23 2147483647 46 1 23 1 46 2 48 2147483647 63 1 48 1 63 2 87 2147483647 8 1 87 1 8 2 73 2147483647 63 1 73 1 63 2 5 2147483647 52 1 5 1 52 2 80 2147483647 21 1 80 1 21 2 31 2147483647 44 1 31 1 44 2 101...
output:
2000 146132
result:
ok 2 number(s): "2000 146132"
Test #8:
score: 10
Accepted
time: 120ms
memory: 4332kb
input:
302 10599 2 72 2147483647 169 1 72 1 169 2 260 2147483647 165 1 260 1 165 2 12 2147483647 108 1 12 1 108 2 16 2147483647 26 1 16 1 26 2 28 2147483647 148 1 28 1 148 2 7 2147483647 74 1 7 1 74 2 139 2147483647 199 1 139 1 199 2 231 2147483647 9 1 231 1 9 2 287 2147483647 123 1 287 1 123 2 135 2147483...
output:
5000 1106316
result:
ok 2 number(s): "5000 1106316"
Test #9:
score: 10
Accepted
time: 145ms
memory: 4228kb
input:
302 10599 2 222 2147483647 132 1 222 1 132 2 17 2147483647 7 1 17 1 7 2 177 2147483647 253 1 177 1 253 2 90 2147483647 195 1 90 1 195 2 128 2147483647 289 1 128 1 289 2 42 2147483647 193 1 42 1 193 2 213 2147483647 133 1 213 1 133 2 263 2147483647 293 1 263 1 293 2 50 2147483647 155 1 50 1 155 2 228...
output:
5000 1290871
result:
ok 2 number(s): "5000 1290871"
Test #10:
score: 10
Accepted
time: 137ms
memory: 4388kb
input:
302 10599 2 176 2147483647 289 1 176 1 289 2 190 2147483647 99 1 190 1 99 2 10 2147483647 96 1 10 1 96 2 240 2147483647 165 1 240 1 165 2 273 2147483647 205 1 273 1 205 2 248 2147483647 194 1 248 1 194 2 220 2147483647 122 1 220 1 122 2 194 2147483647 167 1 194 1 167 2 8 2147483647 67 1 8 1 67 2 227...
output:
5000 1395897
result:
ok 2 number(s): "5000 1395897"