BFS+优先队列:PIPI倒水
问题:
思路:
此题为隐式图BFS题。设三个杯子分别为a,b,c,则状态转移的数目为6,我们可以将水从a倒入b,c;也可将水从b倒入a,c;也可将水从c倒入a,b;题中要求最少倒水量,而非最少操作数,因此我们可以使用优先队列,优先遍历倒水量少的状态。用一个大小为3的一维数组表示三个杯子的水量,连同总倒水量一起作为状态加入队列中。
如何处理每次倒水,要么将倒出的杯子的水倒空,要么将倒入的杯子倒满?设由编号i的杯子倒水入编号j的杯子,i和j的水量分别为w[i],w[j];杯子j的容量为c[j]。则倒水量要么为w[i](i杯子倒空),要么为c[j] – w[j] (j杯子倒满),实际的倒水量则为两者之中的最小值,因为若w[i] > c[j] – w[j],则一定将j杯子倒满,反之同理。倒完水后,w[j]可能被倒满,即w[j] = c[j],也可能未倒满,w[j] = w[j] + w[i],与上述分析同理,倒完水后w[j] 的值也为其中的最小值。倒完水后,w[i]可能为空,即0,也可能为w[i] + w[j] – c[j],实际的值为其中的最大值。
如何建立标记数组?由于总水量是确定的,因此只要知道a,b杯的水量,c的水量也是确定的,状态也是确定的,我们用一个二维数组表示a,b杯水量,作为标记数组。
如何处理若无法达到d,尽量达到接近d的d’?采用暴力的思想,使用一个一维数组ans[],ans[i]表示任意一个杯子达到i升水时,已倒出的最少总水量,在bfs的过程中更新该数组,最终输出结果时从ans[d]从后向前遍历不为初值的元素值即可。
代码:
import java.util.*;
public class Main {
static int[] cap = new int[3];
static int[][] visit = new int[201][201];
static int[] ans = new int[201];
static PriorityQueue<Node> q = new PriorityQueue<>();
static int[] s = {0, 0, 0};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t, c, i, d;
t = scanner.nextInt();
for (c = 0;c < t;c++) {
for (i = 0;i < 3;i++) {
cap[i] = scanner.nextInt();
}
d = scanner.nextInt();
s[2] = cap[2];
Arrays.fill(ans, -1);
for (i = 0;i < 201;i++) {
Arrays.fill(visit[i], 0);
}
q.add(new Node(s, 0));
bfs(d);
for (i = d;i >= 0;i--) {
if (ans[i] != -1) {
System.out.println(ans[i] + " " + i);
break;
}
}
}
}
static void bfs(int d) {
Node now;
int i, j, k, f;
while (!q.isEmpty()) {
now = q.poll();
for (i = 0;i < 3;i++) {
ans[now.status[i]] = ans[now.status[i]] == -1 ? now.flow : Math.min(ans[now.status[i]], now.flow);
}
for (i = 0;i < 3;i++) {
for (j = 0;j < 3;j++) {
if (j == i || now.status[i] == 0) {
continue;
}
int temp[] = new int[3];
for (k = 0;k < 3;k++) {
temp[k] = now.status[k];
}
f = Math.min(temp[i], cap[j] - temp[j]);
temp[j] = Math.min(temp[j] + temp[i], cap[j]);
temp[i] = Math.max(0, temp[i] + now.status[j] - cap[j]);
if (visit[temp[0]][temp[1]] == 0) {
visit[temp[0]][temp[1]] = 1;
q.add(new Node(temp, now.flow + f));
}
}
}
}
}
}
class Node implements Comparable {
public int[] status;
public int flow;
public Node(int[] status, int flow) {
this.status = status;
this.flow = flow;
}
@Override
public int compareTo(Object o) {
Node a = (Node) o;
if (this.flow > a.flow) {
return 1;
} else if (this.flow < a.flow) {
return -1;
}
return 0;
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/153752.html