BFS+优先队列：PIPI倒水

港控/mmm° 2023-10-06 19:34 45阅读 0赞

## BFS+优先队列：PIPI倒水 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

此题为隐式图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\]从后向前遍历不为初值的元素值即可。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]

#### 代码： ####

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;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/39f372f5250744a5a3d588ab2c476607.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/560d64b9a2964914be92fed029e7733e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/d503a29c548e451fafdc348a282c324b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16