题目大意：经典的倒水问题。

给你三个瓶子，体积为a,b,c。

刚開始a。b是空的，c是满的，如今要求你到出体积为d的水。倒水的规则为，要么倒水方为空，要么接水方满

问倒到容量为d时，倒水的最小体积是多少。假设不能倒出体积为d的水，找出d’ < d，最接近d的d’和最小的体积

解题思路：刚才时以为直接bfs，用vis标记一下就结束了，结果WA了。为什么会WA。由于我这样求的是倒水次数最少的，而不是倒水体积最小的，WA是肯定的了

接着将vis数组改成int型的，纪录达到这个状态时倒水的体积。结果可想而之TLE(可能是我写搓了。。)

借鉴了一下别人的，恍然大悟，用一个数组代表倒出这个体积的水时倒的水的最小体积，这样就能够降低非常多种情况了，确实是一个大剪枝

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

#define N 210

#define INF 0x3f3f3f3f

struct Node{

    int have[3];

    int d;

}n1, n2;

int done[N], val[3];

int d;

bool vis[N][N];

void init() {

    memset(vis, 0, sizeof(vis));

    memset(done, 0x3f, sizeof(done));

    scanf("%d%d%d%d", &val[0], &val[1], &val[2], &d);

    done[0] = done[val[2]] = 0;

}

void bfs() {

    queue<Node> Q;

    vis[0][0] = true;

    n1.have[0] = n1.have[1] = n1.d = 0;

    n1.have[2] = val[2];

    Q.push(n1);

    while (!Q.empty()) {

        n1 = Q.front();

        Q.pop();

        for (int i = 0; i < 3; i++)

            for (int j = 0; j < 3; j++) {

                if (i ^ j) {

                    n2 = n1;

                    int tmp = val[j] - n2.have[j] < n2.have[i] ? val[j] - n2.have[j] : n2.have[i];

                    n2.have[j] += tmp;

                    n2.have[i] -= tmp;

                    n2.d += tmp;

                    if (!vis[n2.have[0]][n2.have[1]] || done[n2.have[0]] > n2.d || done[n2.have[1]] > n2.d || done[n2.have[2]] > n2.d) {

                        vis[n2.have[0]][n2.have[1]] = true;

                        for (int k = 0; k < 3; k++) {

                            done[n2.have[k]] = min(done[n2.have[k]], n2.d);

                        }

                        Q.push(n2);

                    }

                }

            }

    }

}

void solve() {

    bfs();

    for (int i = d; i >= 0; i--)

        if (done[i] != INF) {

            printf("%d %d\n", done[i], i);

            break;

        }

}

int main() {

    int test;

    scanf("%d", &test);

    while (test--) {

        init();

        solve();

    }

    return 0;

}