UVALive7264 2015北京现场赛 Kejin Game(拆点+网络流)

题意:

学技能,技能间有前置关系。

  • 学完要求的前置技能后可花x学该技能
  • 不管前置条件,直接花y学该技能
  • 用z的花费消除某个前置关系

求学到技能S所需的最少花费。

1. 算法的选择

  • 很容易想到图论,题意虽然要求最小费用,但费用流的时间复杂度显然不适合本题。
  • 在最短路和最大流中(应该不会想到其它算法了吧?),显然本题的特征是“层次推进”,而最短路所求的是”单线结果“,因此可以考虑使用最大流。

2. 分析题目

思考学习单个技能的两种途径:

1. 学完前置技能,然后学它2. 直接学它

而在途径1中,“学完前置技能”又可分为两种情况:
(1) 实际学掉前置技能
(2) 消除了这项前置关系
因此设经过某技能点表示学完该技能,那么一个技能点应包含四种相关边以表示费用:

1. 学它的前置所用花费2. 学完前置后学它需要的花费3. 直接学它需要的花费4. 消除它对后继的限制所需的花费

3. 建立模型

to be continued.

4. 拆点建图

0%