如家大神书上的例题。第一次接触也是按代码敲得。敲的过程感觉很直观。但自己写估计会写的乱七八糟。以后不能砍得难就不愿意做这种题。否则只能做一些水题了。（PS：48）
紫书
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = ;
struct Node
{
int v[];
int dist; //总倒水量
bool operator < (const Node& a) const
{
return dist > a.dist;
}
};
int vis[maxn][maxn], ans[maxn];
int cap[];
void update_ans(const Node& u)
{
for(int i = ; i < ; i++)
{
int d = u.v[i]; //当前状态下每个杯的水量;
if(ans[d] < || u.dist < ans[d])
ans[d] = u.dist;
}
}
void solve(int a, int b, int c, int d)
{
cap[] = a; cap[] = b; cap[] = c;
memset(vis, , sizeof(vis));
memset(ans, -, sizeof(ans));
priority_queue<Node> q; //优先队列应用！ Node start;
start.v[] = ; start.v[] = ; start.v[] = c; start.dist = ;
q.push(start); vis[][] = ;
while(!q.empty())
{
Node u = q.top(); q.pop(); //选择倒水量少的扩展
update_ans(u);
if(ans[d] >= ) break;
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
{//把水从i倒入j
if(i == j) continue;
if(u.v[i] == || u.v[j] == cap[j]) continue; //i没水或j满
int amount = min(cap[j], u.v[i]+u.v[j]) - u.v[j]; //从i倒入j中水的量
Node v;
memcpy(&v, &u, sizeof(u));
v.v[i] -= amount; v.v[j] += amount; v.dist += amount;
if(!vis[v.v[]][v.v[]]) //状态记忆；因总水量一定，故只知道其中两个杯子的水量就可知当前状态。故记忆数组用二维即可
{
vis[v.v[]][v.v[]] = ;
q.push(v);
}
}
}
while(d >= ) //若达不到，则尽可能接近
{
if(ans[d] >= )
{
printf("%d %d\n", ans[d], d);
return ;
}
d--;
}
}
int main()
{
int T; scanf("%d", &T);
while(T--)
{
int a, b, c, n;
scanf("%d%d%d%d", &a, &b, &c, &n);
solve(a, b, c, n);
}
return ;
}
P205.直接上代码