此题是一道经典的搜索题，但其实又是一道经典的“隐式图最短路”问题。

将当前三个杯子中的水量 \((x,y,z)\) 视作“结点”，结点之间的路径长度即为倒水量。题目中要求求解倒水量最少，即求 \((0,0,c)\) 与某一结点 \(u\) 之间的最短路，其中 \(u\) 的某一杯子中的水量为 \(d\) 或 \(d'\)

很明显这个图的边权都为正数，因此可以用 Dijkstra 算法。

需要注意：

1. 状态的存储：由前两个杯子中的水量即可确定第三只杯子中的水量
2. 答案的更新：有可能有多个结点的水量中都包含\(d\)，因此利用每一个已经得到最短路的结点的\(dist\)对答案进行更新

用\(Dijkstra\)算法很容易做出这道题

//Copyright(C)Corona.//2018-09-28//Dijkstra#include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXN=200+1;int vis[MAXN][MAXN],dis[MAXN][MAXN];int cap[3],ans[MAXN];struct Node{    int v[3],dist;    Node(int a=0,int b=0,int c=0,int d=0)    {        v[0]=a;v[1]=b;v[2]=c;        dist=d;    }    bool operator < (const Node& rhs)    const{        return dist > rhs.dist;    }};void update_ans(Node u){    for(int i=0;i<3;i++)    {        int amount=u.v[i];        if(ans[amount] < 0 || ans[amount] > u.dist)        {            ans[amount] = u.dist;        }    }}void Dijkstra(int a,int b,int c,int d){    cap[0]=a;cap[1]=b;cap[2]=c;    memset(ans,-1,sizeof(ans));    memset(vis,0,sizeof(vis));    memset(dis,0x7f,sizeof(dis));       priority_queue
       
        Q;    Q.push(Node(0,0,c,0));    dis[0][0]=0;    while(!Q.empty())    {        Node u=Q.top();Q.pop();        if(vis[u.v[0]][u.v[1]])continue;        vis[u.v[0]][u.v[1]] = 1;        update_ans(u);        for(int i=0;i<3;i++)            for(int j=0;j<3;j++)                if(i != j)                {                    int amount=min(u.v[i],cap[j]-u.v[j]);//将 i 中的水倒入 j 中;                    Node x=u;                    x.v[i] -= amount;x.v[j] += amount;                    x.dist = u.dist + amount;                    if(!vis[x.v[0]][x.v[1]] && dis[x.v[0]][x.v[1]] > x.dist)                    {                        dis[x.v[0]][x.v[1]] = x.dist;                        Q.push(x);                    }                }    }}void print_ans(int aim){    for(int d=aim;d>=0;d--)        if(ans[d] >=0 )        {            cout << ans[d] <<" "<< d <
        
         > T;    while(T--)    {        int a,b,c,d;        cin >>a>>b>>c>>d;        Dijkstra(a,b,c,d);        print_ans(d);    }    return 0;}
        
       
      
     
    

但是如果用\(Bellman-Ford\)算法的话,需要注意一点小细节

比如下面的程序,看似很正确,就是经典的\(Bellman-Ford\)算法应用.但是如和上面的\(Dijkstra\)对拍一下,会发现几组数据,比如:

1 90 149 94

1 8 10 5

\(Bellman-Ford\)算法都不能得到正确结果.

经过很长长长长长时间的调(瞎)试(搞),我终于发现了问题:

当要将一个结点塞入队列时,如果队列里已经有了这个元素,所以不会重复入队

问题就出在这里,比如这次结点 \((0,1,3)\) 的最短路从\(10\)更新到了\(6\) , 发现\((0,1,3)\) 已经在队列中,于是不再重复入队,可当从队列取出\((0,1,3)\)这个元素去更新其他结点时,

程序中是从队列中拿出了一个结构体变量,用Node类型的dist成员来代表最短路,可是此时u.dist的值是\(10\)而非\(6\)!

改正的方法也很简单,只要在弹出队首元素后更新一下它的dist就可以了

即在Q.pop()后加一句u.dist=dis[u.v[0]][u.v[1]]

又是一行的问题

//Copyright(C)Corona.//2018-11-05//Bellman_Ford #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN = 200+1;int dis[MAXN][MAXN],ans[MAXN],cap[3];int inq[MAXN][MAXN];struct Node{    int v[3],dist;    Node(int a=0,int b=0,int c=0,int d=0)    {        v[0]=a;v[1]=b;v[2]=c;        dist=d;    }};void update_ans(Node u){    for(int i=0;i<3;i++)    {        int amount=u.v[i];        if(ans[amount] < 0 || ans[amount] > u.dist)        {            ans[amount] = u.dist;        }    }    }void print_ans(int aim){    for(int d=aim;d>=0;d--)        if(ans[d] >=0 )        {            cout << ans[d] <<" "<< d <
        
         Q;void Bellman_Ford(int a,int b,int c,int d){    cap[0]=a;cap[1]=b;cap[2]=c;    memset(ans,-1,sizeof(ans));    memset(dis,0x7f,sizeof(dis));       memset(inq,0,sizeof(inq));    Q.push(Node(0,0,c,0));    dis[0][0]=0;    inq[0][0]=true;    while(!Q.empty())    {        Node u=Q.front();        Q.pop();        inq[u.v[0]][u.v[1]]=0;        update_ans(u);        for(int i=0;i<3;i++)            for(int j=0;j<3;j++)                if(i != j)                {                    int amount=min(u.v[i],cap[j]-u.v[j]);//将 i 中的水倒入 j 中;                    Node x=u;                    x.v[i] -= amount;                    x.v[j] += amount;                    x.dist = u.dist + amount;                    if(dis[x.v[0]][x.v[1]] > x.dist)                    {                        dis[x.v[0]][x.v[1]] = x.dist;                        if(!inq[x.v[0]][x.v[1]])                        {                            Q.push(x);                            inq[x.v[0]][x.v[1]]=1;                        }                    }                }    }}int main(){    int T;    cin >> T;    while(T--)    {        int a,b,c,d;        cin >>a>>b>>c>>d;        Bellman_Ford(a,b,c,d);        print_ans(d);    }    return 0;}