嘘~ 正在从服务器偷取页面 . . .

UVA10603 倒水问题 Fill 题解

发布日期: 2023-05-25

更新日期: 2023-05-25

文章字数: 520

UVA10603 倒水问题 Fill 题解

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

数据范围：

$1\le a,b,c,d \le 200$ 。

把状态用 $(a,b,c)$ 表示，倒水就变成了一个最短路问题

难点是代码吧，需要理清思路再写。

时间复杂度 $\mathcal{O}(n^3\log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(215))

int a,b,c,d,ans[N],cap[3]; char vis[N][N];
struct node { int v[3] = {0}, d = 0; };
bool operator<(node x,node y) { return x.d > y.d; }
priority_queue<node> q;
void update(node x)
{
    for(int i = 0; i < 3; i++)
        if(ans[x.v[i]] < 0 || x.d < ans[x.v[i]]) ans[x.v[i]] = x.d;
}
void solve()
{
    cap[0] = a; cap[1] = b; cap[2] = c;
    memset(vis, 0, sizeof(vis)); memset(ans, -1, sizeof(ans));
    while(!q.empty()) q.pop(); node x, now, tmp; x.v[2] = c;
    for(q.push(x), vis[0][0] = true; !q.empty(); )
    {
        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++)
            {
                if(now.v[i] == 0 || now.v[j] == cap[j]) continue;
                int w = min(cap[j], now.v[i] + now.v[j]) - now.v[j];
                tmp = now; tmp.v[i] -= w; tmp.v[j] += w; tmp.d += w;
                if(vis[tmp.v[0]][tmp.v[1]] == false) {
                    vis[tmp.v[0]][tmp.v[1]] = true; q.push(tmp);
                }
            }
    }
    for(; ~d; --d) if(ans[d] >= 0) {
        return cout << ans[d] << ' ' << d << '\n', void(0);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) { cin >> a >> b >> c >> d; solve(); }
    return 0;
}