CiC_iCi 表示重量,WiW_iWi 表示价值
设想是这样的:建图,先从源点向 nnn 个点分别连一条容量 ∞\infty∞,费用 000 的边,nnn 个点向 ttt 连一条容量 M/CiM/C_iM/Ci,费用 WiW_iWi 的边。ttt 向汇点连一条容量 MMM,费用 000 的边。
然后每条边加一个 label,nnn 个点向 ttt 连的边和反向边加一个 CiC_iCi 的 label,表示流经这条边的权,就是前面的流流过来要乘 CiC_iCi。记录两种流量(加权和不加权的),最大化加权流量。求可行性