QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#477766 | #602. 最小费用最大流(随机数据) | NOI_AK_ME# | 0 | 0ms | 0kb | C++20 | 3.5kb | 2024-07-14 10:07:06 | 2024-07-14 10:07:07 |
Judging History
answer
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
typedef long long i64;
i64 rd()
{
i64 k = 0, f = 1;
char s = getchar();
while (s < '0' || s > '9')
{
if (s == '-')
f = 0;
s = getchar();
}
while (s >= '0' && s <= '9')
{
k = (k << 1) + (k << 3) + (s ^ '0');
s = getchar();
}
return f ? k : -k;
}
void wr(i64 x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar((x % 10) ^ '0');
}
// 1-indexed
namespace MCMF
{
using cap = i64;
const int N = 505;
const int M = 15005;
const i64 flow_INF = 1145141919810114514ll;
const i64 cost_offset = 1145141919;
int n, m, s, t;
struct edge
{
int to, nxt;
cap flow, cost;
} e[M << 1];
int cnt;
int h[N];
void init_sz(int _n) { n = _n, m = 0, cnt = 1; }
int add_edge(int u, int v, cap flow, cap cost, bool directed = true)
{
++m;
e[++cnt].to = v, e[cnt].nxt = h[u], e[cnt].flow = flow, e[cnt].cost = cost;
h[u] = cnt;
e[++cnt].to = u, e[cnt].nxt = h[v], e[cnt].flow = directed ? 0 : flow, e[cnt].cost = -cost;
h[v] = cnt;
return cnt;
}
int tme;
int vis[N], fa[N], fae[N];
void dfs(int u)
{
vis[u] = 1;
for (int i = h[u], v; i; i = e[i].nxt)
if (!vis[v = e[i].to] && e[i].flow)
fa[v] = u, fae[v] = i, dfs(v);
}
int pi[N];
int phi(int x)
{
if (vis[x] == tme)
return pi[x];
vis[x] = tme;
return pi[x] = phi(fa[x]) - e[fae[x]].cost;
}
int cyc[N];
i64 cost;
void clr()
{
memset(h, 0, sizeof(h));
tme = 0;
memset(vis, 0, sizeof(vis)), memset(fa, 0, sizeof(fa)), memset(fae, 0, sizeof(fae));
memset(pi, 0, sizeof(pi)), memset(cyc, 0, sizeof(cyc));
}
void pushflow(int id)
{
int pen = e[id ^ 1].to, lca = e[id].to;
++tme;
while (pen)
vis[pen] = tme, pen = fa[pen];
while (vis[lca] != tme)
vis[lca] = tme, lca = fa[lca];
int e2 = 0, f = e[id].flow, path = 2, clen = 0;
for (int i = e[id ^ 1].to; i != lca; i = fa[i])
{
cyc[++clen] = fae[i];
if (e[fae[i]].flow < f)
f = e[fae[e2 = i] ^ (path = 0)].flow;
}
for (int i = e[id].to; i != lca; i = fa[i])
{
cyc[++clen] = fae[i] ^ 1;
if (e[fae[i] ^ 1].flow < f)
f = e[fae[e2 = i] ^ (path = 1)].flow;
}
cyc[++clen] = id;
for (int i = 1; i <= clen; ++i)
{
e[cyc[i]].flow -= f, e[cyc[i] ^ 1].flow += f;
cost += 1ll * f * e[cyc[i]].cost;
}
if (path == 2)
return;
int lste = id ^ path, lst = e[lste].to, now = e[lste ^ 1].to;
while (lst != e2)
{
vis[now]--, lste ^= 1;
std::swap(lste, fae[now]);
std::swap(lst, fa[now]);
std::swap(lst, now);
}
}
std::pair<cap, cap> solve(int _s, int _t)
{
s = _s, t = _t;
int lhead = h[s], rhead = h[t];
add_edge(t, s, flow_INF, -cost_offset);
dfs(t);
vis[t] = tme = 2, fa[t] = cost = 0;
for (int i = 2, pre = cnt; i != pre; i = (i == cnt ? 2 : i + 1))
if (e[i].flow && e[i].cost < phi(e[i ^ 1].to) - phi(e[i].to))
pushflow(pre = i);
h[s] = lhead, h[t] = rhead;
cnt -= 2; // extra operation if calculate minimum flow or other.
return std::make_pair(e[cnt + 2].flow, cost + 1ll * e[cnt + 2].flow * cost_offset);
}
}
int main()
{
int n = rd(), m = rd(), s = rd(), t = rd();
MCMF::init_sz(n);
while (m--)
{
int u = rd(), v = rd(), flow = rd(), cost = rd();
MCMF::add_edge(u, v, flow, cost);
}
std::pair<i64, i64> ans = MCMF::solve(s, t);
wr(ans.first), putchar(' '), wr(ans.second);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
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:
result:
Test #2:
score: 0
Runtime Error
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:
result:
Test #3:
score: 0
Runtime Error
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:
result:
Test #4:
score: 0
Runtime Error
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:
result:
Test #5:
score: 0
Runtime Error
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:
result:
Test #6:
score: 0
Runtime Error
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:
result:
Test #7:
score: 0
Runtime Error
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:
result:
Test #8:
score: 0
Runtime Error
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:
result:
Test #9:
score: 0
Runtime Error
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:
result:
Test #10:
score: 0
Runtime Error
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...