解题思路：这是神奇的一题，一定要好好体会。见代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 const int maxn = 205; 7 int vis[maxn][maxn], ans[maxn], cap[3]; 8 9 struct node{ 10 int v[3], cnt; 11 friend bool operator <(node A, node B){ 12 return A.cnt > B.cnt; //cnt更小的优先级更高 13 } 14 }; 15 16 priority_queue<node> q; //优先队列 17 18 void Change(node u) 19 { 20 for(int i = 0; i < 3; i++) 21 { 22 int d = u.v[i]; 23 //ans[d] < 0表示该点目前没有访问过 24 //找出走到容量为d的点时所倒水的最小总量 25 if(ans[d] < 0 || u.cnt < ans[d]) ans[d] = u.cnt; 26 } 27 return ; 28 } 29 30 void solve(int a, int b, int c, int d) 31 { 32 cap[0] = a, cap[1] = b, cap[2] = c; //初始化三个杯子的容量 33 node s, s1; 34 //每个杯子中初始状态所含有的水 35 s.v[0] = 0, s.v[1] = 0, s.v[2] = c, s.cnt = 0; 36 vis[0][0] = 1; //标记第一个和第二个杯子中水的状态已经出现过 37 while(!q.empty()) q.pop(); 38 q.push(s); 39 40 while(!q.empty()) 41 { 42 s = q.top(); 43 q.pop(); 44 45 Change(s); //好好体会 46 if(ans[d] >= 0) break; //表示已经符合题意，可以跳出 47 48 //从杯子i中把水倒到杯子j中 49 for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) 50 { 51 if(i == j) continue; //不可能倒水到自身 52 if(s.v[i] == 0 || s.v[j] == cap[j]) continue;//i为空或j已经满 53 int tmp = min(s.v[i], cap[j] - s.v[j]); //到底倒完i还是将j倒满 54 s1 = s; //s的状态要保存下来，还要进行下一次循环。 55 //杯子i中的水增加，j中的水减少，总转移两增加 56 s1.v[i] = s.v[i] - tmp, s1.v[j] = s.v[j] + tmp, s1.cnt = s.cnt + tmp; 57 if(!vis[s1.v[0]][s1.v[1]]) //如果这种状态之前没出现过 58 { 59 vis[s1.v[0]][s1.v[1]] = 1; 60 q.push(s1); //入队列 61 } 62 } 63 64 } 65 while(d >= 0) 66 { 67 if(ans[d] >= 0) //符合条件，刚好为题目所说的d，或与它接近 68 //的最小符合条件的数 69 { 70 printf("%d %d ", ans[d], d); 71 return ; //直接返回 72 } 73 d --; 74 } 75 return ; 76 } 77 78 int main() 79 { 80 int t, a, b, c, d; 81 scanf("%d", &t); 82 while(t --) 83 { 84 scanf("%d %d %d %d", &a, &b, &c, &d); 85 86 memset(vis, 0, sizeof(vis));//一定要初始化 87 memset(ans, -1, sizeof(ans)); 88 89 solve(a, b, c, d); 90 } 91 return 0; 92 }