Fill - UVA 10603

网址如下：

Fill - UVA 10603 - Virtual Judge (vjudge.net)

感觉有点浮躁，没法完全将思绪投入题的思考中

脑袋糊糊的

一道bfs题

代码如下：

#include<queue>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

const int maxn = 201;

struct Node{
    int v[3], dist;
    Node(){}
    Node(int a, int b, int c, int dist):dist(dist){v[0] = a; v[1] = b; v[2] = c;}
    bool operator<(const Node tmp)const{return dist > tmp.dist;}
    bool update_ans(void);
};
int vis[maxn][maxn];
int cap[3], d, ans, V;

bool Node::update_ans(void){
    if(vis[v[0]][v[1]] && dist >= vis[v[0]][v[1]]) return false;

    vis[v[0]][v[1]] = dist;
    for(int i = 0; i < 3; i++){
        if(v[i] > ans && v[i] <= d){ans = v[i]; V = dist;}
        else if(v[i] == ans) V = V < dist ? V : dist;
    }
    return true;
}
void init(void){
    ans = V = 0;
    memset(vis, 0, sizeof(vis));
}
void bfs(void){
    std::priority_queue<Node> q; q.push(Node(0, 0, cap[2], 0));
    while(!q.empty()){
        Node tmp = q.top(); q.pop();
        if(tmp.update_ans()){
            //开始倒水
            for(int u = 0; u < 3; u++){
                for(int v = 0; v < 3; v++){
                    if(u == v || !tmp.v[u] || tmp.v[v] == cap[v]) continue;
                    int val = std::min(tmp.v[u], cap[v] - tmp.v[v]);
                    int chg[3]{}; chg[v] = val; chg[u] = -val;
                    q.push(Node(tmp.v[0] + chg[0], tmp.v[1] + chg[1], tmp.v[2] + chg[2], tmp.dist + val));
                }
            }
        }
    }
}

int main(void)
{
    int T; scanf("%d", &T);
    while(T--){
        init(); scanf("%d%d%d%d", &cap[0], &cap[1], &cap[2], &d);
        if(cap[2] <= d) ans = cap[2];
        else bfs();
        printf("%d %d\n", V, ans);
    }

    return 0;
}

我这代码的可读性……还可以吧？

vis是记录目前状态下的最小的倒水量，下标分别代表a，b杯的水量，因为总水量不变，故不记录c杯的水量

其他应该没什么问题