:::info[Description] Link. :::
:::infoSolution 好玩的来了。
考虑对于一条 的边，其初始给定的容量为 ，流量为 ，则需要分类讨论 和 之间的大小关系：
此时当前的容量是合法的，有下面的几种操作方式：
- 减少流量：每减少 就需要让 减少 ，花费 的代价。本质可以看作是撤销原来一单位的 流量，也就是让费用流沿着反方向 走一单位。边的容量为 ，费用为 。
- 增加流量，但是不超过 ：每增加 就需要让 增加 ，花费 的代价。 的边容量为 费用为 。
- 增加流量且超过 ：容量和费用都需要增加 ，因此花费 的代价。 的边容量为 费用为 。
这条边初始就不合法，因此需要先花费 的代价平衡容量和流量，然后再进行操作。同样需要分类讨论：
- 首先需要把前 单位的流量退流，连一条 容量为 费用为 的边，然后提前增加 的代价即可。
- 然后如果要继续退流，则每单位的代价为 ，连一条 容量为 费用为 的边即可。
- 如果要增加流量，则每单位的代价为 ，连一条 容量为 费用为 的边即可。
然后还需要考虑流量不守恒的问题。记 表示 点当前的出流减去当前的入流是多少。则对于一条边 而言，初始先更新 。处理完后如果 则说明这个点流进来的流量太多了，因此从超级源点 向 点连一条容量为 费用为 的边即可；如果 则说明这个点流出的流量太多了，因此从 点向超级汇点 连一条容量为 费用为 的边即可。
因为 号点和 号点不要求流量守恒，所以额外加一条从 号结点连向 号结点的流量为 费用为 的边即可。
最后算答案只需要跑一遍从 点到 点的最小费用最大流，然后求出最小的费用就是答案。 :::
:::success[Code]
namespace lowspeed_song {
inline void init() {
}
namespace MCMF {
int S, T, hhh[N], e[N], f[N], ne[N], w[N], idxx, q[N], d[N], pre[N], incf[N], st[N];
inline void ae(int a, int b, int c, int d) {
e[idxx] = b, w[idxx] = d, f[idxx] = c, ne[idxx] = hhh[a], hhh[a] = idxx++;
e[idxx] = a, w[idxx] = -d, f[idxx] = 0, ne[idxx] = hhh[b], hhh[b] = idxx++;
}
inline int spfa() {
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = inf;
while (hh != tt) {
int t = q[hh++];
if (hh == N) hh = 0;
st[t] = 0;
for (int i = hhh[t]; ~i; i = ne[i]) {
int v = e[i];
if (f[i] && d[v] > d[t] + w[i]) {
d[v] = d[t] + w[i];
pre[v] = i, incf[v] = min(incf[t], f[i]);
if (!st[v]) {
q[tt++] = v;
if (tt == N) tt = 0;
st[v] = 1;
}
}
}
}
return incf[T] > 0;
}
inline void ek(int &F, int &C) {
F = C = 0;
while (spfa()) {
int tt = incf[T];
F += tt, C += tt * d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1]) f[pre[i]] -= tt, f[pre[i] ^ 1] += tt;
}
}
}
int d[N];
inline void sol([[maybe_unused]]int __testcase_id) {
int n, m; cin >> n >> m;
memset(MCMF::hhh, -1, sizeof MCMF::hhh);
int res = 0;
while (m--) {
int u, v, c, f; cin >> u >> v >> c >> f, d[u] += f, d[v] -= f;
if (f <= c) MCMF::ae(v, u, f, 1), MCMF::ae(u, v, c - f, 1), MCMF::ae(u, v, inf, 2);
else res += f - c, MCMF::ae(v, u, f - c, 0), MCMF::ae(v, u, c, 1), MCMF::ae(u, v, inf, 2);
} MCMF::ae(n, 1, inf, 0), MCMF::S = n + 1, MCMF::T = n + 2;
for (int i = 1; i <= n; ++i)
if (d[i] > 0) MCMF::ae(i, MCMF::T, d[i], 0);
else if (d[i] < 0) MCMF::ae(MCMF::S, i, -d[i], 0);
int F, C; MCMF::ek(F, C);
cout << res + C << '\n';
}
} // namespace lowspeed_song:::
难度：黑-
鲜活指数：8
喜欢的话，留下你的评论吧～