【题解】UVa 10603【Fill】

分析

假设某一时刻,第一个杯子里有$v_0$升水,第二个杯子里有$v_1$升水,第三个杯子中有$v_3$升水,称当时的状态为$(v0,v1,v2)$。将其看为一个图,则跑一个图论就好了。

代码

#include<cstdio>
#include<queue>
#include<cstring>
using std::priority_queue;using std::min;
class Node{
public:
    int v[3],dis;
    bool operator < (const Node &rhs) const {
        return dis > rhs.dis;
    }
};

const int MAXN = 200 + 6;
bool hash[MAXN][MAXN];
int cap[3],ans[MAXN];

void updateAns(const Node &u){
    for(int i = 0;i < 3;i++){
        int d= u.v[i];
        if(ans[d] < 0 || u.dis < ans[d]) ans[d] = u.dis;
    }
}

void solve(int a,int b,int c,int d){
    cap[0] = a;cap[1] = b;cap[2] = c;
    memset(hash,0,sizeof(hash));
    memset(ans,-1,sizeof(ans));
    priority_queue<Node> Q;

    Node s;
    s.dis = 0;
    s.v[0] = 0;s.v[1] = 0;s.v[2] = c;
    Q.push(s);

    hash[0][0] = true;
    while(Q.size()){
        Node u = Q.top();Q.pop();
        updateAns(u);
        if(ans[d] >= 0) break;
        for(int i = 0;i < 3;i++){
            for(int j = 0;j < 3;j++){
                if(i != j){
                    if(u.v[i] == 0 || u.v[j] == cap[j]) continue;
                    int ant = min(cap[j],u.v[i] + u.v[j]) - u.v[j];
                    Node v;
                    memcpy(&v,&u,sizeof(u));
                    v.dis = u.dis + ant;
                    v.v[i] -= ant;
                    v.v[j] += ant;
                    if(!hash[v.v[0]][v.v[1]]){
                        hash[v.v[0]][v.v[1]] = true;
                        Q.push(v);
                    }
                }
            }
        }
    }

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

    return 0;
}