rt,本蒟蒻口胡了一个费用流做法,思路如下:
- 建立一个源点s,从s向所有“S”连一条容量为1,费用为0的边。
- 建立一个汇点t,从所有“E”向t连一条容量为inf,费用为0的边。
- 对于每一个点,向所有下一步能到达的点连一条容量为inf,费用为当前节点种类所需时间的边。
- 因为题目只需一种“S”到“T”的方案,所以我又建立了一个新汇点tt,从t向tt连一条容量为1,费用为0的边。
- 建完图,跑最小费用最大流,若最大流为0,则表示无解。
本蒟蒻按上述做法成功通过了所有样例,但交上去只有0分,想了好久还是没有发现错在哪里,跪求大佬点拨!