倒水问题fill-UVa 10603

---

每天坚持做算法题，熟悉基本的套路，巩固语言基础，总结经验记下所学所想。

题目

测试输入

1

1 12 15 7

测试输出

14 7

HINT

bfs+prioqueue,队列扩展优先总倒水量小的

代码

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 200 + 5;

struct WaterNode{
    int v[3];
    int dist;
    WaterNode ():dist(0){}
    bool operator < (const WaterNode& rhs) const{
        return dist > rhs.dist;
    }
};

int ans[maxn];// ans[d]表示得到d升水的最小水量
int cap[3];// 每杯水的容量
int book[maxn][maxn];

void updateAns(const WaterNode& n){
    for (int i = 0; i < 3; ++i) {
        if (ans[n.v[i]] < 0 || ans[n.v[i]] > n.dist)
            ans[n.v[i]] = n.dist;
    }
}

void bfs(int a, int b, int c, int d){

    cap[0] = a;cap[1] = b;cap[2] = c;
    memset(book, 0, sizeof(book));
    memset(ans, -1, sizeof(ans));

    priority_queue<WaterNode> waterQueue;

    WaterNode start;
    start.v[0] = 0; start.v[1] = 0; start.v[2] = c;
    waterQueue.push(start);
    book[0][0] = 1;

    while(!waterQueue.empty()){

        WaterNode fro = waterQueue.top();

        // 更新ans
        updateAns(fro);

        if(ans[d] >= 0) break;

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (i != j){
                    // i往j倒水
                    if (fro.v[i] == 0 || fro.v[j] == cap[j]) continue;

                    WaterNode nextNode;
                    memcpy(nextNode.v, fro.v, sizeof(fro.v));

                    int amount = min(cap[j], fro.v[i]+fro.v[j]) - fro.v[j];
                    nextNode.v[i] -= amount;
                    nextNode.v[j] += amount;

                    nextNode.dist = fro.dist + amount;

                    if (!book[nextNode.v[i]][nextNode.v[j]]){
                        book[nextNode.v[i]][nextNode.v[j]] = 1;
                        waterQueue.push(nextNode);
                    }


                }
            }
        }
        waterQueue.pop();

    }

    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);
        bfs(a, b, c, d);
    }
    return 0;
}

总结

bfs求最短路径