QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#603629 | #602. 最小费用最大流(随机数据) | shiqiaqiaya | 100 ✓ | 778ms | 4256kb | C++17 | 9.1kb | 2024-10-01 17:55:27 | 2024-10-01 17:55:27 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using i64 = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K> using rb_tree = tree<K, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const i64 mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);
template<class type = int>
struct Dinic : vector<vector<int>> { // O(n^2 * m),二分图最大匹配 O(n^0.5 * m)
struct Edge {
int v;
type c;
Edge(int v, type c) : v(v), c(c) {}
};
vector<Edge> e;
vector<int> cur, h;
Dinic(int n) : vector(n) {}
void add(int u, int v, type c) {
at(u).emplace_back(e.size()), e.emplace_back(v, c);
at(v).emplace_back(e.size()), e.emplace_back(u, 0);
}
int bfs(int & s, int & t) {
h.assign(size(), numeric_limits<int>::max());
queue<int> q;
h[s] = 0, q.emplace(s);
while (q.size()) {
int u = q.front(); q.pop();
for (auto & i : at(u)) {
auto & [v, c] = e[i];
if (c > 0 && h[v] > h[u] + 1) h[v] = h[u] + 1, q.emplace(v);
}
}
return h[t] != numeric_limits<int>::max();
}
type dfs(int u, int & t, type flow) {
if (u == t) return flow;
type ret = flow, a;
for (int & i = cur[u]; i < at(u).size(); i++) {
auto & [v, c] = e[at(u)[i]];
if (c > 0 && h[v] == h[u] + 1 && (a = dfs(v, t, min(ret, c)))) {
ret -= a, c -= a, e[at(u)[i] ^ 1].c += a;
if (ret == 0) return flow;
}
}
return flow - ret;
}
type maxflow(int s, int t, type flow = 0) {
while (bfs(s, t)) {
cur.assign(size(), 0), flow += dfs(s, t, numeric_limits<type>::max());
}
return flow;
}
};
template<class type = int>
struct ISAP : vector<vector<int>> { // O(n^2 * m)
struct Edge {
int v;
type c;
Edge(int v, type c) : v(v), c(c) {}
};
vector<Edge> e;
vector<int> cur, h, gap;
ISAP(int n) : vector(n) {}
void add(int u, int v, type c) {
at(u).emplace_back(e.size()), e.emplace_back(v, c);
at(v).emplace_back(e.size()), e.emplace_back(u, 0);
}
void bfs(int & t) { // 反向bfs
h.assign(size(), numeric_limits<int>::max()), gap.assign(size() + 2, 0);
queue<int> q;
h[t] = 0, gap[h[t]]++, q.emplace(t);
while (q.size()) {
int u = q.front(); q.pop();
for (auto & i : at(u)) {
auto & [v, c] = e[i];
if (e[i ^ 1].v && h[v] > h[u] + 1) h[v] = h[u] + 1, gap[h[v]]++, q.emplace(v);
}
}
}
type dfs(int u, int & s, int & t, type flow) {
if (u == t) return flow;
type ret = flow, a;
for (int & i = cur[u]; i < at(u).size(); i++) {
auto & [v, c] = e[at(u)[i]];
if (c > 0 && h[v] + 1 == h[u] && (a = dfs(v, s, t, min(ret, c)))) {
ret -= a, c -= a, e[at(u)[i] ^ 1].c += a;
if (ret == 0) return flow;
}
}
if (--gap[h[u]] == 0) h[s] = size();
return gap[++h[u]]++, flow - ret;
}
type maxflow(int s, int t, type flow = 0) {
for (bfs(t); h[s] < size(); ) {
cur.assign(size(), 0), flow += dfs(s, s, t, numeric_limits<type>::max());
}
return flow;
}
};
template<class type = int>
struct HLPP : vector<vector<int>> { // O(n^2 * sqrt(m))
struct Edge {
int v;
type c;
Edge(int v, type c) : v(v), c(c) {}
};
vector<Edge> e;
vector<int> h, gap;
int level = 0;
vector<type> ex;
vector<stack<int>> B;
HLPP(int n) : vector(n) {}
void add(int u, int v, type c) {
at(u).emplace_back(e.size()), e.emplace_back(v, c);
at(v).emplace_back(e.size()), e.emplace_back(u, 0);
}
int bfs(int & s, int & t) { // 反向bfs
h.assign(size(), numeric_limits<int>::max()), gap.assign(size() + 2, 0);
queue<int> q;
h[t] = 0, gap[h[t]]++, q.emplace(t);
while (q.size()) {
int u = q.front(); q.pop();
for (auto & i : at(u)) {
auto & [v, c] = e[i];
if (e[i ^ 1].v && h[v] > h[u] + 1) h[v] = h[u] + 1, gap[h[v]]++, q.emplace(v);
}
}
return h[s] != numeric_limits<int>::max();
}
int push(int u, int & s, int & t) {
int init = u == s;
for (auto & i : at(u)) {
auto & [v, c] = e[i];
if (!init && h[u] != h[v] + 1 || !c || h[v] == numeric_limits<int>::max()) continue;
type k = init ? c : min(c, ex[u]);
if (v != s && v != t && !ex[v]) B[h[v]].push(v), level = max(level, h[v]);
ex[u] -= k, ex[v] += k, c -= k, e[i ^ 1].c += k;
if (!ex[u]) return 0;
}
return 1;
}
void relabel(int u) {
h[u] = numeric_limits<int>::max();
for (auto & i : at(u)) {
if (e[i].c) h[u] = min(h[u], h[e[i].v]);
}
if (++h[u] < size()) B[h[u]].push(u), level = max(level, h[u]), ++gap[h[u]];
}
int slect() {
for ( ; level > -1 && B[level].size() == 0; level--);
return level == -1 ? 0 : B[level].top();
}
type maxflow(int s, int t, type flow = 0) {
if (!bfs(s, t)) return 0;
ex.assign(size(), 0), B.assign(size(), stack<int>());
h[s] = size(), push(s, s, t);
for (int u = 0; u = slect(); ) {
B[level].pop();
if (push(u, s, t)) {
if (--gap[h[u]] == 0) for (int i = 0; i < size(); i++) {
if (i != s && h[i] > h[u] && h[i] < size() + 1) h[i] = size() + 1;
}
relabel(u);
}
}
return ex[t];
}
};
template <class type = int>
struct MCMF : vector<vector<int>> {
struct Edge {
int v;
type c, f; // 容量,费用
Edge(int v, type c, type f) : v(v), c(c), f(f) {}
};
vector<Edge> e;
vector<type> h, dis;
vector<int> pre;
MCMF(int n) : vector(n) {}
void add(int u, int v, type c, type f) {
at(u).emplace_back(e.size()), e.emplace_back(v, c, f);
at(v).emplace_back(e.size()), e.emplace_back(u, 0, -f);
}
int dijkstra(int & s, int & t) {
dis.assign(size(), numeric_limits<type>::max()), pre.assign(size(), -1);
std::priority_queue<pair<type, int>, vector<pair<type, int>>, greater<>> q;
dis[s] = 0, q.emplace(0, s);
while (q.size()) {
auto [d, u] = q.top(); q.pop();
if (dis[u] < d) continue;
for (auto & i : at(u)) {
auto & [v, c, f] = e[i];
if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
dis[v] = d + h[u] - h[v] + f, pre[v] = i;
q.emplace(dis[v], v);
}
}
}
return dis[t] != numeric_limits<type>::max();
}
void spfa(int & s, int & t) { // 存在负权边
h.assign(size(), numeric_limits<type>::max());
vector<int> vis(size());
queue<int> q;
h[s] = 0, vis[s] = 1, q.push(s);
while (q.size()) {
int u = q.front(); q.pop(), vis[u] = 0;
for (auto & i : at(u)) {
auto & [v, c, f] = e[i];
if (c > 0 && h[v] > h[u] + f) {
h[v] = h[u] + f;
if (!vis[v]) vis[v] = 1, q.push(v);
}
}
}
}
array<type, 2> mncmxf(int s, int t, int flag, type flow = 0, type cost = 0) {
if (flag) spfa(s, t); // 若存在负权边,也可以使用消负权法
else h.assign(size(), 0); // 若全为正权值
while (dijkstra(s, t)) {
type a = numeric_limits<type>::max();
for (int i = 0; i < size(); h[i++] += dis[i]);
for (int i = t; i != s; a = min(a, e[pre[i]].c), i = e[pre[i] ^ 1].v);
for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
e[pre[i]].c -= a, e[pre[i] ^ 1].c += a;
}
flow += a, cost += a * h[t];
}
return {flow, cost};
}
};
void QAQ() {
int n, m;
cin >> n >> m;
MCMF adj(n + 1);
for (int i = 0, u, v, c, f; i < m; i++) {
cin >> u >> v >> c >> f;
adj.add(u, v, c, f);
}
auto [flow, cost] = adj.mncmxf(1, n, 0);
cout << flow << " " << cost << "\n";
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int t = 1;
// cin >> t;
for (cout << fixed << setprecision(12); t--; QAQ());
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3720kb
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: 3692kb
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: 3916kb
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: 25ms
memory: 4008kb
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: 91ms
memory: 3884kb
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: 96ms
memory: 3876kb
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: 95ms
memory: 3848kb
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: 750ms
memory: 4256kb
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: 778ms
memory: 4192kb
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: 753ms
memory: 4252kb
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"