状态空间搜索/Dijkstra/Uva10603/路径输出/刘佳汝紫书P202

很多求最短最长最多做少的问题都可以归结为图的遍历，但是这些图往往不是程序事先给你读入的，是由程序动态生成的。 ——刘佳汝

此题来源于https://vjudge.net/problem/UVA-10603

题目简述：
给3个杯子容量分别为a,b,c，最初只有第三个杯子装满了c升水，其他两个杯子都是空的。最少需要来回倒多少水才（第一个杯子往第二个杯子里倒了3升，倒过的水的总量就是）能让某一个杯子中的水有d升？如果无法做到恰好d升，就让某一个杯子里的水是d1升，其中d1<d升(1<=a,b,c,d<=200)。要求输出最少的倒水量和目标水量。

此时，看一眼题目有点像智力题，仅凭凑很难得出答案，因为每次可以选择的倒水方案有好几个，而每一个的下一次倒水方案也有很多。

这时，我们需要把当前三个杯子状态看成一个点，而每一个倒水方案的操作看成边，而通过可行的操作形成的另一个三个杯子状态看成当前状态的邻接点，此时就构造了一个隐式图，而题目要求最少倒水量，所以是个带权图，需要用到优先队列总是选择倒水量最小（权值最小）的边(Dijkstra)。（如果权值都相同或者是个无权图BFS即可） 搜索题另一个不得不提的点是判重：在这里因为只有三个杯子，每个杯子的容量都不是很大，可以直接开个3维数组判重，但是在这因为三个杯子的水加起来是固定，也就是说x1+x2+x3=d，如果前两个杯子的水一样了，最后一个杯子的水肯定一样，所以我们只要开一个二维数组就可以了。 另外这题还有个关键点，那就是有可能是搜不到最终理想状态（某个杯子里的水为d升），我们就需要开一个数组把每升水下的最少倒水量都记录下来，最后从d升还是向下递减访问，访问到第一个最接近d升的输出。

附上代码（路径输出后面会提到）：

#include #include #include #include #include #include using namespace std; int n; int capacity[4]; struct state{ int bottle[3]; int dist; state():dist(0){ memset(bottle,0,sizeof(bottle)); } bool operator t.dist; } }; int vis[200][200]; int ans[200]; //记录下答案 void update_ans(const state& cur){ for(int i = 0;i cur.dist) ans[d] = cur.dist; } } void bfs(){ priority_queue min_heap; //min_heap state Ini; Ini.bottle[2] = capacity[2]; min_heap.push(Ini); vis[0][0] = 1; memset(ans,-1,sizeof(ans)); //初始化为-1，代表没被取到过 while(min_heap.size()){ state cur = min_heap.top(); min_heap.pop(); update_ans(cur); if(ans[capacity[3]] >= 0) break; for(int i = 0;i < 3;++i){ for(int j = 0;j 0){ if(ans[i] >= 0){ printf("%d %d\n",ans[i],i); return; } i--; } } int main(void){ scanf("%d",&n); while(n--){ memset(vis,0,sizeof(vis)); scanf("%d%d%d%d",&capacity[0],&capacity[1],&capacity[2],&capacity[3]); bfs(); } return 0; } /* 2 2 3 4 2 96 97 199 62 output: 2 2 9859 62 */ 那么如何输出路径呢？ 最简单也是最直接的办法就是在每个状态里都用个动态数组记录下路径，下一个状态拷贝上一个状态的路径，并且把自身也加入这条路径中，很明显这需要消耗大量的内存空间。 每个状态中加入一个成员表示它的父亲结点fa（一个位置下标），这就意味着要把所有访问过的状态结点都放在一个结点数组里，此时fa就是每个结点的父亲结点在数组中的下标，这样就可以通过逐个访问父结点找到来的路径了。但是，此时会发现一个问题：原算法里队首结点拓展边的时候，本身结点只存着父亲结点的下标，而没有本身的下标，下一个节点无法得知父亲结点的下标编号了，所以1.队列中只存结点在node数组中的编号，而不存每个状态结点了 2.在每个状态继续加入一个成员，那就是本身在node数组中的编号（因此会每个状态多增加两个变量）。

下面用第二种方式种的第一个实现：

#include #include #include #include #include #include using namespace std; int n; int capacity[4]; struct state{ int bottle[3]; int dist,fa; state():dist(0),fa(-1){ memset(bottle,0,sizeof(bottle)); } bool operator t.dist; } }; int vis[200][200]; int ans[200]; vector nodes; //这里先用动态数组去存所有状态 因为不明确可能状态的个数 void update_ans(int i){ state cur = nodes[i]; for(int i = 0;i cur.dist) ans[d] = cur.dist; } } struct cmp{ //refine the comparison bool operator()(int a,int b){ //现在最小堆里存的是节点的下标编号 return nodes[a].dist > nodes[b].dist; } }; void print_road(int code){ //通过父结点dfs寻找路径 if(code < 0) return; print_road(nodes[code].fa); for(int i = 0;i < 3;++i) printf("%d ",nodes[code].bottle[i]); printf("\n"); } void bfs(){ priority_queue<int,vector,cmp> min_heap; //min_heap state Ini; Ini.bottle[2] = capacity[2]; //初始状态的c杯是满的 nodes.push_back(Ini); min_heap.push(0); vis[0][0] = 1; int final_code; while(min_heap.size()){ int index = min_heap.top(); //获取倒水量最小的编号 min_heap.pop(); update_ans(index); final_code = index; if(ans[capacity[3]] >= 0) break; //当某个杯子含有d升的时候 就结束搜索 state cur = nodes[index]; for(int i = 0;i < 3;++i){ for(int j = 0;j 0){ if(ans[d] >= 0){ printf("%d %d\n",ans[d],d); //print the road print_road(final_code); return; } d--; } } void Ini(){ //全局变量最好都开个函数重置，不然丢三落四老忘 memset(vis,0,sizeof(vis)); nodes.clear(); memset(ans,-1,sizeof(ans)); //初始化为-1，代表没被取到过 } int main(void){ scanf("%d",&n); while(n--){ Ini(); scanf("%d%d%d%d",&capacity[0],&capacity[1],&capacity[2],&capacity[3]); bfs(); } return 0; } /* 2 2 3 4 2 96 97 199 62 output: 2 2 9859 62 */
作者：Mamba_ZJP

p2 dijkstra 输出