一、题意

每组数据给出a,b,c,d四个值。
a,b,c为三个杯子的容量，其中初始时前两个杯子为空，最后一个装满了水。
d为目标水量。
要求你在这三个杯子之间相互倒水，每次倒水要么源杯倒空，要么把目标杯倒满，不能把水倒掉。
求最少的总倒水量，使得最终至少有一个杯子的水量最接近d。
输出这个最少的总倒水量以及最接近d的那个值。

二、解析

这是一道典型的隐式bfs题目。
老规矩，找状态点！在本题中，状态先就是三个杯子的容量和总倒水量。
为什么状态包括总倒水量呢？因为本题中最短路径中的最短指的是总倒水量最少，因此需要将其算入状态的维度之中，同时需要使用优先队列来使得每次先弹出到水量最小的点。
这样的话vis数组难道要4维？实际不用，因为实际上我们这个倒水量指的是最小倒水量，因此只要有了3个杯子的水量信息就可以唯一确定倒水量了；另外，由于总水量是固定的（不允许把水倒掉），因此我们只需要前两个杯子的水量就可以唯一确定第三个杯子的水量了。综上，我们的vis数组只需要2维即可。

三、代码

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 200 + 5, INF = 1 << 30;
const int Fx[6][2] = {{0, 1}, {0, 2}, {1, 2}, {1, 0}, {2, 0}, {2, 1}};
struct node {
    int val[3], water;
    node() {}
    node(int a, int b, int c, int water) : water(water) {
        val[0] = a, val[1] = b, val[2] = c;
    }
    bool operator < (const node& rhs) const {
        return water > rhs.water;
    }
};
int kase, vol[3], d, ans, d_, vis[maxn][maxn];

bool updateAns(const node& u) {
    for(int i = 0; i < 3; i ++) {
        int a = u.val[i];
        if(a == d) {
            ans = u.water, d_ = d;
            return 1;
        }
        else if(a < d && (d - a) < (d - d_)) {
            ans = u.water, d_ = a;
        }
    }
    return 0;
}

void pour(node& v, int x, int y) {
    int & xw = v.val[x];
    int & yw = v.val[y];
    int pw = min(xw, vol[y] - yw);
    xw -= pw, yw += pw;
    v.water += pw;
}

void bfs() {
    priority_queue<node> que;
    que.push(node(0, 0, vol[2], 0)), vis[0][0] = 1;
    while(!que.empty()) {
        node u = que.top();
        que.pop();
        if(updateAns(u)) break;
        for(int k = 0; k < 6; k ++) {
            node v = u;
            pour(v, Fx[k][0], Fx[k][1]);
            if(vis[v.val[0]][v.val[1]]) continue;
            que.push(v), vis[v.val[0]][v.val[1]] = 1;
        }
    }
    cout << ans << " " << d_ << endl;
}

int main() {
    cin >> kase;
    while(kase --) {
        cin >> vol[0] >> vol[1] >> vol[2] >> d;
        memset(vis, 0, sizeof(vis));
        ans = INF, d_ = -INF;
        bfs();
    }
}

四、归纳

  • 可以通过分析状态的唯一性来合理减小vis数组的维度，以避免空间不足。