玄关!关于网络瘤拆点。
  • 板块学术版
  • 楼主WhiteNight__
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/1/19 13:45
  • 上次更新2025/1/19 16:23:50
查看原帖
玄关!关于网络瘤拆点。
1098596
WhiteNight__楼主2025/1/19 13:45

以此题为例:P2045 方格取数加强版

题解做法:把每个网格点拆为 x_{x}y_{y} 两种点,ix>iyi_{x} -> i_{y} 连两条边,一条流量为 11,费用为 ai,ja_{i,j};另一条流量为 kk,费用为 00。相邻的边用流量 kk,费用 00 的边相连。跑最大费用最大流。AC。

我的做法:把两个相邻的网格点(可以到达)用两条边相连,一条流量 11,费用 ai,ja_{i,j};另一条流量 kk,费用 00。WA。

自认为这两种连边方案的效果大概相同,但结果不同,希望得到解答。

2025/1/19 13:45
加载中...