题目大意:

给出N种药水的价格,然后给出一些形如A B C 的关系,表示 A药水+B药水 可以组合出 C药水(保证 A+B 不会得到多种药水)。 要求得到1号药水的最少花费和相应的方案数。

N<=1000。

解题过程:

1.一开始没考虑到会有环的情况(比如A+B=C,B+C=A),想成了树形dp,还以为是大水题,结果全部WA了。

2.正解:还是转化为图论的模型,这里是dijkstra的变形:

D[i]表示得到药水i的最小花费,根据dijkstra的的思想,当前D[i]最小的那个必然就是药水i的最小花费。那么只要N次就可以求出所有药水的最小花费。

然后根据dijkstra的流程,每次找到一个最小的D[i],然后不断去更新其他的D[j]。只不过是通过一个药水k,去更新father[i][k],要求药水k的最小花费已经确定下来了。

也就是D[j]=min{D[j], D[i]+D[k]}   (father[i][k]=j && vis[k]=true).

总结:所谓的最短路,并不一定只有在有实际的“路"的题目中才用得到,关键是把题目转化为图论模型,把更新条件转化为”路“。此题没有对dijkstra算法贪心的精髓理解深刻是难以转化为图论模型的。

04-26 10:01