UVa #10603 Fill （例题7-8）

看了书上的解法，自己写了一遍，几乎没遇到什么障碍。不过看Board上面的讨论，觉得细节上需要注意的地方还是挺多的。。纯粹自己写肯定分分钟跪下

1、vis数组只用开两维

看到讨论中大家都是用的三维数组vis[201][201][201]，其实有了两杯水的数据，第三杯水可以用总量减去两杯水的量得到，所以不需要维护3维数组

2、解的存储

因为题目说如果取不到d，就要打印出比d小的最大的可能解d'以及倒水的量，所以bfs就把所有可能的d以及倒水量都存了下来，如果之前取到过这个d，则判断倒水量是否比之前的少，如果满足要求的话就更新数据。最后从d开始往下减小，遇到第一个取到过的解就打印并返回

3、优先队列

首先要注意这道题问的是倒水量最少，而不是倒水次数最少，而这两者没有必然关系。所以在bfs的时候，就不能用普通queue存储需要遍历的节点，而应该用一个优先队列，让倒水量少的排在前头。

另外在讨论中看到很多人用的是dfs，并且很多人得了TLE。然后大家比较推荐的解法是dijkstra。

Labels