UVA10603 倒水问题 Fill 题解

· · 题解

题目大意

三个容量分别为a,b,c的容器，初始状态只有c装满，a,b都为空，需要计算出如何最少需要倒多少升水才能让其中某一个杯子中的水有d升。如果能够找到这样的d，你还是需要计算出其中某一个杯子达到d升时，最少需要倒多少升水。

状态设置

怎么标记一个状态有没有出现过呢？ 如果用一个三维数组表示，我们发现总数是一定的，最后一维一定是确定的，那么它就没有作用了，因此可以用一个二维数组表示状态，v[i][j]表示a有i升水，b有j升水是否出现过，状态总数 201 \times 201。

对于一个状态，可以用结构体来存储，还要存储到这个状态需要的倒水数，那么怎么让倒水数最少呢？考虑用优先队列来维护这个状态，以倒水数为关键字排序。

模拟过程

模拟从三个水桶里面的倒水过程，注意每个水桶有最大的容量，而且水桶容量不能为0。

答案统计

如果目标水量已经出现过直接终止操作。否则就找最接近的。

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int a,b,c,d,T,cap[3];
bool v[210][210];
int ans[210];
struct Node{
    int v[3];
    int d;
    bool operator < (const Node& j) const{
        return d>j.d;
    }
};
void update(const Node& x)
{
    for(int i=0;i<3;i++)
    {
        int t=x.v[i];
        if(ans[t]<0||x.d<ans[t]) ans[t]=x.d;
    }
}
void solve(int a,int b,int c,int d)
{
    cap[0]=a;cap[1]=b;cap[2]=c;
    priority_queue<Node> q;
    memset(v,0,sizeof(v));
    memset(ans,-1,sizeof(ans));
    Node x; 
    x.v[0]=0;x.v[1]=0;x.v[2]=c;x.d=0;
    q.push(x);
    v[0][0]=1;
    while(!q.empty())
    {
        Node now=q.top();
        update(now);
        q.pop();
        if(ans[d]>=0) break;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                Node t;
                if(now.v[i]==0||now.v[j]==cap[j]) continue;
                int p=min(cap[j],now.v[i]+now.v[j])-now.v[j];
                t=now;
                t.v[i]-=p;
                t.v[j]+=p;
                t.d+=p;
                if(!v[t.v[0]][t.v[1]])
                {
                    v[t.v[0]][t.v[1]]=1;
                    q.push(t);
                }
            }
        }
    }
    while(d>=0)
    {
        if(ans[d]>=0)
        {
            printf("%d %d\n",ans[d],d);
            return;
        }
        d--;
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        solve(a,b,c,d);
    }
}