好不容易建完了博客，当然要发一篇助助兴了，今天就是我拖了两天的倒水问题，对于这道题我也是给上了隐式图的标签，因为这个BFS藏得还是有点深的。
我相信很多人小时候都玩过智力测试题吧，有这么一道题，讲的是有三个杯子a,b,c,通过来回倒水使得我们可以得到一个杯子里正好有d毫升的水。所以呢，今天这道题就是这个问题的拓展，这个问题是这样的：
输入a，b，c，d四个数字，同样的也是三个杯子a，b，c。一开始，a杯子和b杯子都是空的，而c杯子则是满的，我们一次只能选择两个杯子（例如c杯子往a杯子中倒水），倒水的规则是，要么出水的那个杯子空了则停止，要么接水的杯子满了停止，其他情况都不在规则内。不停地在这三个杯子中作操作，使得最终有一个杯子到达了d的水量。同时，题目给出了难点：当任何情况都满足不了d水量时，我们去找离d最近的小于d的水量，将其作为答案。而且，题目要求输出的最优解不是倒水的步数最少，而是倒水的水量最少（这个大家可以自己思考一下，参考刘汝佳老师给的例子：1 12 15 7，步数最少并不等于移动水量最少）
所以这道题我们需要枚举状态，我们可以将a杯子的水变成一个维度，再讲b杯子的水变成一个维度，将状态转化为二维数组（当然这是为了剪枝，记录是否访问过，在具体枚举的时候得存储结构体），由于总水量已经确定不变（他又不能把水倒掉），所以我们无需再添加第三个维度。
剪枝的问题已经解决了，接下来我们来解决一下如何计算最小水量的问题，众所周知BFS是一个靠步数（就是距离）所决定先后访问次序的算法，那么这道题我们既然不要求步数，而是要求了水量，我们如何建立一种先后机制来使程序先访问移动水量少的节点来完成找到答案呢？
没错，就是上图中的优先队列（priority_queue），不过，这次优先队列不再是大的先出队，反而是小的先出队，所以我们需要在结构体中重载它使得它以移动的水量water来排序。这样我们就可以轻松地为BFS建立革命性的“规矩”使得BFS改头换面般地完美运用于这道题中。
那么我们来解决最后一个问题，如何当答案不存在时能找到最近的小于d的答案来代替呢？我们这里可以用一种很容易想到的又很巧妙的方法来解决，我们新建一个从0到最大水量的所有情况的一维数组，只要出现了一种水位我们就把它对应的数组值改为该水位状态下的移动水量，所以当我们找不到正确答案时，我们只需要从d不断减1，知道我们找到被访问过的位置，那就是近似的答案。
以下为AC代码（紧跟刘老师的步伐）：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using namespace std;
const int maxn=210;
int ans[maxn],vis[maxn][maxn],cap[3];//我们只需二维的vis数组即可确定状态，因为水的总量已经确定了
struct Node{
int v[3],water;//每一个状态节点记录每一个杯中水的数量以及到现在所倒的水量
bool operator < (const Node& A) const{//由于优先队列从大到小，所以我们重载成从小到大，更直观
return water>A.water;
}
Node(int c){
this->v[2]=c;
this->v[0]=0;
this->v[1]=0;
this->water=0;
}
Node(){}
};
void update(const Node& node){//更新ans数组，为求近似值用
for(int i=0;i<3;i++){
int d=node.v[i];//这时候不需要再分A，B，C杯子了，只要记录杯中水的数量即可
if(ans[d]<0||ans[d]>node.water)//因为题目中并没有指定必须哪个杯子输出答案
ans[d]=node.water;
}
}
void bfs(int a,int b,int c,int d){
memset(vis,0, sizeof(vis));
memset(ans,-1,sizeof(ans));//ans 不能初始化为0，因为可能有不用倒水的情况（题目中明确说明）
priority_queue<Node> que;//使用优先队列
cap[0]=a,cap[1]=b,cap[2]=c;//为什么使用数组呢，因为后面的i和j
Node start(c);
que.push(start);
vis[0][0]=1;//不要忘记起始状态
while(!que.empty()){
Node u=que.top();
que.pop();
update(u);
if(ans[d]>=0)//正统的出口（就是存在标准答案）
break;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(i!=j){
if(u.v[i]==0||u.v[j]==cap[j])//每次枚举都是单向的，所以当v[i]为空时退出
continue;
int move=min(cap[j],u.v[i]+u.v[j])-u.v[j];//算出倒的水量
Node u2;
memcpy(&u2,&u, sizeof(u));//直接内存拷贝效率更高
u2.v[i]-=move,u2.v[j]+=move;//改变杯中水量
if(!vis[u2.v[0]][u2.v[1]]) {
u2.water+=move;//移动的水量增加
vis[u2.v[0]][u2.v[1]]=1;
que.push(u2);
}
}
}
}
}
while(true){
if(ans[d]>=0) {
cout << ans[d] << ' ' << d << endl;
break;
}
d--;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;
while(cin>>T){
while(T--){
int a,b,c,d;
cin>>a>>b>>c>>d;
bfs(a,b,c,d);
}
}
return 0;
}
日更啦日更啦，明天还有一道路径寻找题，然后攻占IDA*！！