疑问,关于拆点的建图......
查看原帖
疑问,关于拆点的建图......
699650
Ciaxin_楼主2023/1/15 22:58

源点 s\text s 向第 ii 个仓库建边,流量为 aia_i,费用为 00,第 ii 个仓库向汇点 t\text t 建边,流量为 1ni=1nai\frac{1}{n}\sum_{i=1}^{n}a_i,费用为 00,其他按题意建边(流量为 inf\text{inf},费用为 11)。


# 疑惑起

虽然建图只需将每个仓库建一个点(可AC)即可,但是某人开始拆了点,流量为 inf\text{inf},费用为 00

但是只有 18pts18\text{pts},AC #1 and #7。其他答案貌似比正解小。所以这样建图有何不妥? [18pts code]

2023/1/15 22:58
加载中...