关于月赛div2的D题
  • 板块学术版
  • 楼主_outcast_
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/10/16 20:58
  • 上次更新2023/11/4 03:34:48
查看原帖
关于月赛div2的D题
376125
_outcast_楼主2021/10/16 20:58

rt,本蒟蒻口胡了一个费用流做法,思路如下:

  • 建立一个源点s,从s向所有“S”连一条容量为1,费用为0的边。
  • 建立一个汇点t,从所有“E”向t连一条容量为inf,费用为0的边。
  • 对于每一个点,向所有下一步能到达的点连一条容量为inf,费用为当前节点种类所需时间的边。
  • 因为题目只需一种“S”到“T”的方案,所以我又建立了一个新汇点tt,从t向tt连一条容量为1,费用为0的边。
  • 建完图,跑最小费用最大流,若最大流为0,则表示无解。

本蒟蒻按上述做法成功通过了所有样例,但交上去只有0分,想了好久还是没有发现错在哪里,跪求大佬点拨!

2021/10/16 20:58
加载中...