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