当前没有测试数据。

题目：Sanhai 与多重残暴机制

背景故事

luogu 的管理机制越来越残暴：

1. 流量限制：每条链路有容量上限。
2. 费用陷阱：每条链路有单位费用，可能为负（补贴），但系统保证无负环。
3. 强制清算：系统会在任意时刻触发“清算”，清算后所有路径上的流量必须被切割成若干段，每段重新计费。
4. 多目标约束：Sanhai 不仅要把数据送到用户电脑，还要满足每个用户的最低需求，否则会被封号。
5. 优先级机制：不同用户有不同的优先级权重，若无法满足所有需求，必须优先保证高优先级用户的需求。

题目描述

给定一个有向图 $G=(V,E)$：

• 节点 1 是源点（Sanhai 的服务器）。
• 有 $k$ 个用户节点，每个用户 $i$ 有：
  • 最小需求 $L_i$
  • 最大需求 $R_i$（可能为无穷大）
  • 优先级权重 $w_i$

每条边 $(u,v)$ 有：

• 容量 $cap(u,v)$
• 单位费用 $cost(u,v)$

系统允许至多 $b$ 次“清算”，等价于把整个传输过程分成 $b+1$ 个阶段。每个阶段的流量独立计费，但边的容量是全局共享的。

你的任务是：

1. 在容量与费用约束下，最大化所有用户的总流量。
2. 若存在多种最大流方案，优先保证高优先级用户的需求（即按字典序比较 $(f_1,f_2,...,f_k)$)，其中 $f_i$ 是用户 $i$ 的流量，权重高的用户排在前面）。
3. 在满足 1 和 2 的前提下，使总代价最小。

输入格式

n m k b
u1 v1 cap1 cost1
...
um vm capm costm
id1 L1 R1 w1
...
idk Lk Rk wk

• $n$：节点数 $1 ≤ n ≤ 500$
• $m$：边数 $0 ≤ m ≤ 10^4$
• $k$：用户数
• $b$：允许的清算次数
• 每条边：起点 $u$，终点 $v$，容量 $cap$，费用 $cost$
• 每个用户：编号 $id$，最小需求 $L$，最大需求 $R$（可为无穷大），优先级权重 $w$

输出格式

maxFlow minCost

难点分析

• 多阶段流量：清算机制要求把流量分段，但容量全局共享 → 需要在建模时引入“阶段层图”。
• 多目标优化：既要最大流，又要满足用户的最小需求，还要按优先级字典序比较 → 需要分层次优化。
• 费用最小化：在前两层目标固定后，再做最小费用 → 需要多次调用最小费用最大流，或在费用函数中引入大权重字典序技巧。
• 复杂度：需要 O($b·MCMF$) 或者更高阶的费用流 + 线性规划思想。

提示

• 可以通过 超级源$超级汇 建模用户需求：
  • 超级源连到每个用户节点，容量 = $R_i$，费用 = 0。
  • 每个用户节点连到超级汇，容量 = $R_i$，费用 = 0。
  • 为保证最小需求 $L_i$，可以先强制流 $L_i$，再在剩余容量上跑费用流。
• 优先级字典序可通过 费用加权放大 技巧实现：给高优先级用户的流量附加极大权重，使得优化顺序正确。
• 清算机制可通过 时间分层图 建模：复制图 $b+1$ 层，每层容量共享，费用独立计。