倒水问题UVA 10603——隐式图&&Dijkstra

题目

给你三个容量分别为 $a,b,c$ 的杯子，最初只有第3个杯子装满了水，其他两个杯子为空。最少需要到多少水才能让一个某个杯子中的水有 $d$ 升呢？如果无法做到恰好 $d$ 升，就让某个杯子里的水是 ${d}'$ 升，其中 ${d}' < d$ 并且尽量接近 $d$。（$1 \leq a,b,c,d \leq 200$）

分析

设第一个杯子有 $v_0$ 升水、第二个杯子有 $v_1$ 升水、第三个杯子有 $v_2$ 升水，称这为一个状态 $((v_0, v_1, v_2))$，而从一个杯子向另一个杯子倒水则扩展出下一个状态，设倒水量为两个状态间的距离。类似于Dijkstra，因此能保证每次从队列中弹出的都是距离最小的，每次都更新一下答案。

由于总水量是不变的，也就是说 $v_0, v_1$ 确定时，$v_2$ 也随之确定，所以实际状态数为 $200^2$.

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

struct Node {

  int v[], dist;

  bool operator < (const Node& rhs) const {

    return dist > rhs.dist;

  }

};

const int maxn =  + ;

int mark[maxn][maxn], dist[maxn][maxn], cap[], ans[maxn];

void update_ans(const Node& u) {

  for(int i = ; i < ; i++) {

    int d = u.v[i];

    if(ans[d] <  || u.dist < ans[d]) ans[d] = u.dist;

  }

}

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

  cap[] = a; cap[] = b; cap[] = c;

  memset(ans, -, sizeof(ans));

  memset(mark, , sizeof(mark));

  memset(dist, -, sizeof(dist));

  priority_queue<Node> q;

  Node start;

  start.dist = ;

  start.v[] = ; start.v[] = ; start.v[] = c;

  q.push(start);

  dist[][] = ;

  while(!q.empty()) {

    Node u = q.top(); q.pop();

    if(mark[u.v[]][u.v[]]) continue;

    mark[u.v[]][u.v[]] = ;

    update_ans(u);

    if(ans[d] >= ) break;

    for(int i = ; i < ; i++)

      for(int j = ; j < ; j++) if(i != j) {

        if(u.v[i] ==  || u.v[j] == cap[j]) continue;

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

        Node u2=u;

        u2.dist = u.dist + amount;  //换成+1,就是求最少次数

        u2.v[i] -= amount;

        u2.v[j] += amount;

        int& D = dist[u2.v[]][u2.v[]];

        if(D <  || u2.dist < D){

          D = u2.dist;

          q.push(u2);

        }

      }

  }

  while(d >= ) {

    if(ans[d] >= ) {

      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 ;

}