关于 M 为 1e18 级别的网络流背包可行性
  • 板块学术版
  • 楼主Akwamaryna
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/24 12:01
  • 上次更新2023/10/27 18:40:35
查看原帖
关于 M 为 1e18 级别的网络流背包可行性
182533
Akwamaryna楼主2022/7/24 12:01

CiC_i 表示重量,WiW_i 表示价值

设想是这样的:建图,先从源点向 nn 个点分别连一条容量 \infty,费用 00 的边,nn 个点向 tt 连一条容量 M/CiM/C_i,费用 WiW_i 的边。tt 向汇点连一条容量 MM,费用 00 的边。

然后每条边加一个 label,nn 个点向 tt 连的边和反向边加一个 CiC_i 的 label,表示流经这条边的权,就是前面的流流过来要乘 CiC_i。记录两种流量(加权和不加权的),最大化加权流量。求可行性

2022/7/24 12:01
加载中...