Question

pascal 关于图中的路径问题

给定一个图的每条边连接哪两个点，并给出每条边的权值和可以经过的次数，要求从原点出发，走一条最长的路径。
以下是原题：
【问题描述】
对于一场gank来说，配合的默契是十分重要的，技能的连接有时能决定一场gank的成败。于是，KSF决定对技能的连接做一些更好的设计。
技能一般分为先手技能和后手技能两种，先手技能是在任何情况下都可以释放的，而后手技能不同，它对于释放时目标的状态有一些要求，但是它却比一般的先手技能更加强大，因此，我们往往以先手技能做铺垫，使目标达到释放后手技能的要求，以便使用更加强大的后手技能。
【输入数据】skills.in
第一行：n，表示接下来有多少个技能输入，
第2~n+1行：每行4个数，x，a，b，k，表示着个技能对目标造成x的伤害，需要目标的状态为a才能使用该技能，使用后目标状态变为b，可以使用k次。若a等于0，则说明这个技能是先手技能，没有初始条件的要求；若b等于0，则说明这个技能不改变目标的状态。
【输出数据】skills.out
一个数，表示一系列的技能释放后，对目标可以造成的最大伤害。

讲下解法，不需要代码，讲的好的追加。。
在线等。。。。。。
能不能说下dp的方法？
大概可以做多大范围？
费用流不大会。。。
另外，没有终点。。。看下题。。
哦。。。知道了。。

Answer 1

费用流

对于每条边，容量设置为可以经过的次数，费用设置为边的权值。
另加一个源点，与起点连一条容量为1，费用为0的边，
再加一个汇点，从终点连一条容量为1，费用为0的边。

然后用缩圈的费用流算法求解即可。

PS:这题的数据范围多少？如果比较小可以直接用搜索或者状态压缩动态规划

Answer 2

呵呵。。。“没有终点”，看来你是没怎么看网络流的东西啊。。可以自己设一个终点，与所有末状态连边即可。 楼上说的费用流是可以的。

不过如果 技能的种数在 20以内就可以用状态压缩做。 因为2^20=10^6，时间空间还是可以承受的。