Fill-倒水问题(Uva-10603-隐式图路径寻找问题)

原题：https://uva.onlinejudge.org/external/106/10603.pdf

---

有三个没有刻度的杯子，它们的容量分别是a, b, c, 最初只有c中的杯子装满水，其他的被子都是空的。问如果通过倒水得到d升水， 若可以得到，还要求最少的倒水总量（每倒一次水，都加入到总量里）。若不能得到d升水，求比d小的距离d最近的d'升水， 及最少倒水总量。

---

分析：

因为是求最少倒水总量，本能地想到用bfs搜索。最开始读错题了...看成求倒水的最少次数，这个很简单.....我们可以把求解的过程看成是空间状态的搜索，每一个状态都有一组a, b, c, pour_amount (分别对应三个杯子里的水量和到达当前状态需要的倒水总量)。如果把每个状态想象成一个结点， 整个搜索的过程就是图的遍历过程。

---

难点：

这道题的每一个状态有四个变量，所以要考虑所有四种变量的所有变化情况。方法是每次枚举当前a,b,c的下一个可达结点。这里有一个可以回溯剪枝的要点，就是结点判重，如果下一个结点的a,b,c曾经遍历过且它的pour_amount小于当前的pour_amount，回溯.结点判重的时候还有一个难点就是自己实现一个哈希表.对于一个状态a,b,c，对应一个到达这个状态的最小pour_amount

如果用stl自带的map，速度非常慢，比如1000组数据需要耗时4s左右

然而如果用自己实现的hash_map，1000组数据只要0.003s

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int MAXHASHSIZE = ;

 int d, _head[MAXHASHSIZE], _next[MAXHASHSIZE];

 int vol[], _d, ans, idx, st[MAXHASHSIZE], pour_set[MAXHASHSIZE];

 struct Node {

     int v[], pour;

     Node(int a = , int b = , int c = , int p = ) {

         v[] = a; v[] = b; v[] = c; pour = p;

     }

     bool operator == (const Node &rhs) const {

         for (int i = ; i < ; i++) if (rhs.v[i] != v[i]) return false;

         if (rhs.pour != pour) return false;

         return true;

     }

 };

 void init() {

     _d = -;

     ans = ;

     idx = ;

     memset(_head, , sizeof(_head));

 }

 bool try_to_insert(Node &cur) {

     int status = cur.v[] *  + cur.v[] *  + cur.v[];

     int h = status % MAXHASHSIZE;

     int u = _head[h];

     while (u) {

         if (st[u] == status) {

             if (cur.pour < pour_set[u]) {

                 pour_set[u] = cur.pour;

                 return ;

             }

             return ;

         }

         u = _next[u];

     }

     st[idx] = status;

     pour_set[idx] = cur.pour;

     _next[idx] = _head[h];

     _head[h] = idx++;

     return ;

 }

 void bfs(Node start) {

     pour_set[] = start.pour;

     try_to_insert(start);

     queue<Node> q;

     q.push(start);

     while (!q.empty()) {

         Node cur = q.front(); q.pop();

         for (int i = ; i < ; i++) {

             if (cur.v[i] == _d)

                 ans = min(ans, cur.pour);

             else if (cur.v[i] > _d && cur.v[i] <= d) {

                 ans = cur.pour;

                 _d = cur.v[i];

             }

             if (cur.v[i] != )

                 for (int j = ; j < ; j++) if (i != j) {

                     int pour = min(cur.v[i], vol[j] - cur.v[j]);

                     cur.v[i] -= pour;

                     cur.v[j] += pour;

                     Node nextn = Node(cur.v[], cur.v[], cur.v[], cur.pour + pour);

                     cur.v[i] += pour;

                     cur.v[j] -= pour;

                     if (try_to_insert(nextn)) q.push(nextn);

                 }

         }

     }

 }

 int main() {

     int T;

     scanf("%d", &T);

     while (T--) {

         init();

         scanf("%d%d%d%d", &vol[], &vol[], &vol[], &d);

         bfs(Node(, , vol[], ));

         printf("%d %d\n", ans, _d);

     }

     return ;

 }

---