题目：Fill
题意：有3个容积为a，b，c的杯子，最初a、b为空，c中装满水。每次可以从一个杯子向另一个杯子倒水，但只有把一个杯子倒空或把另一个杯子倒满时才能停止。如果要使其中一个杯子中有d升水，求最少倒水的的体积。若无法满足 ，则目标水量要比d小且和d尽量接近。
思路：
同书上思路，用priority_queue代替queue，比用队列快。
详见对刘汝佳代码的注释。
思路1见：uva 10603 Fill
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<deque>
#include<queue>
#include<algorithm>
#include<sstream>
using namespace std;#define n 3
#define m 205struct Node {int x[n];int step;Node() {}Node(Node y[],int s) {memcpy(x,y,sizeof(x));step=s;}Node(int one,int two,int three,int s) {x[0]=one,x[1]=two,x[2]=three,step=s;}bool operator <(const Node& other) const {if(step>other.step) return true;if(step<other.step) return false;for(int i=0; i<n; i++) {if(x[i]<other.x[i]) return true;if(x[i]>other.x[i]) return false;}return false;}
};int d;
Node M;
bool use[m][m];
int ans[m],dis[m][m];void init() {memset(use,0,sizeof(use));memset(ans,-1,sizeof(ans));memset(dis,-1,sizeof(dis));
}void bfs(Node IN) {priority_queue<Node> que;que.push(IN);dis[IN.x[0]][IN.x[1]]=0;while(!que.empty()) {Node head=que.top();que.pop();if(use[head.x[0]][head.x[1]]) continue;use[head.x[0]][head.x[1]]=true;for(int i=0; i<n; i++)if(ans[head.x[i]]==-1||ans[head.x[i]]>head.step) ans[head.x[i]]=head.step;if(ans[d]!=-1) break;for(int i=0; i<n; i++) {for(int j=0; j<n; j++) {if(i!=j&&head.x[i]!=0&&head.x[j]!=M.x[j]) {Node ch=head;int move;if(ch.x[i]>=M.x[j]-ch.x[j]) move=M.x[j]-ch.x[j];else move=ch.x[i];ch.x[i]-=move,ch.x[j]+=move,ch.step+=move;if((dis[ch.x[0]][ch.x[1]]==-1||ch.step<dis[ch.x[0]][ch.x[1]])) {dis[ch.x[0]][ch.x[1]]=ch.step;que.push(ch);}}}}}int now=d;while(now>=0) {if(ans[now]>=0){printf("%d %d\n",ans[now],now);return ;}now--;}
}int main() {int T;scanf("%d",&T);while(T--) {int A,B,C;scanf("%d%d%d%d",&A,&B,&C,&d);M=Node(A,B,C,0);init();bfs(Node(0,0,C,0));}return 0;
}刘汝佳的代码+注释：
// UVa10603 Fill
// Rujia Liu
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;struct Node {int v[3], dist; //v[]: 水量 dist:路径 bool operator < (const Node& rhs) const {return dist > rhs.dist;}
};const int maxn = 200 + 5;
int mark[maxn][maxn], dist[maxn][maxn], cap[3], ans[maxn];
//mark[][]: 是否已有这种状态 dist[][]: 杯0中有i升水、1中有j升水时的d' cap[]: 杯子的容量 ans[]: d(d')为i时的最少水量 void update_ans(const Node& u) { //计算ans for(int i = 0; i < 3; i++) {int d = u.v[i];if(ans[d] < 0 || u.dist < ans[d]) ans[d] = u.dist;}
}void solve(int a, int b, int c, int d) { //bfs cap[0] = a;cap[1] = b;cap[2] = c;memset(ans, -1, sizeof(ans));memset(mark, 0, sizeof(mark));memset(dist, -1, sizeof(dist));priority_queue<Node> q; //队列 Node start; //初始状态 start.dist = 0;start.v[0] = 0;start.v[1] = 0;start.v[2] = c;q.push(start);dist[0][0] = 0;while(!q.empty()) {Node u = q.top();q.pop();if(mark[u.v[0]][u.v[1]]) continue; //使用过 mark[u.v[0]][u.v[1]] = 1;update_ans(u);if(ans[d] >= 0) break; //符合条件 for(int i = 0; i < 3; i++) //从杯i倒到杯j for(int j = 0; j < 3; j++) if(i != j) {if(u.v[i] == 0 || u.v[j] == cap[j]) continue; //j中水满或i中无水 int amount = min(cap[j], u.v[i] + u.v[j]) - u.v[j]; //倒的水量 Node u2;memcpy(&u2, &u, sizeof(u));u2.dist = u.dist + amount; //倒水 u2.v[i] -= amount;u2.v[j] += amount;int& D = dist[u2.v[0]][u2.v[1]];if(D < 0 || u2.dist < D) { //加入队列 D = u2.dist;q.push(u2);}}}while(d >= 0) { //输出 if(ans[d] >= 0) {printf("%d %d\n", ans[d], d);return;}d--;}
}int main() {int T, a, b, c, d;scanf("%d", &T);while(T--) { //输入 scanf("%d%d%d%d", &a, &b, &c, &d);solve(a, b, c, d);}return 0;
}