【SPFA算法】作物杂交

题目

3305. 作物杂交 - AcWing题库

---

作物杂交是作物栽培中重要的一步。

已知有 $N$ 种作物 (编号 $1$ 至 $N$ )，第 $i$ 种作物从播种到成熟的时间为 $T_i$ 。

作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。

如作物 $A$ 种植时间为 $5$ 天，作物 $B$ 种植时间为 $7$ 天，则 $AB$ 杂交花费的时间为 $7$ 天。

作物杂交会产生固定的作物，新产生的作物仍然属于 $N$ 种作物中的一种。

初始时，拥有其中 $M$ 种作物的种子 (数量无限，可以支持多次杂交)。

同时可以进行多个杂交过程。

求问对于给定的目标种子，最少需要多少天能够得到。

如存在 $4$ 种作物 $ABCD$ ，各自的成熟时间为 $5$ 天、 $7$ 天、 $3$ 天、 $8$ 天。

初始拥有 $AB$ 两种作物的种子，目标种子为 $D$ ，已知杂交情况为 $A × B → C，A × C → D$ 。

则最短的杂交过程为：

第 $1$ 天到第 $7$ 天 (作物 $B$ 的时间)， $A × B → C$ 。

第 $8$ 天到第 $12$ 天 (作物 $A$ 的时间)， $A × C → D$ 。

花费 $12$ 天得到作物 $D$ 的种子。

输入格式

输入的第 $1$ 行包含 $4$ 个整数 $N, M, K, T$ ， $N$ 表示作物种类总数 (编号 $1$ 至 $N$ )， $M$ 表示初始拥有的作物种子类型数量， $K$ 表示可以杂交的方案数， $T$ 表示目标种子的编号。

第 $2$ 行包含 $N$ 个整数，其中第 $i$ 个整数表示第 $i$ 种作物的种植时间 $T_i$ 。

第 $3$ 行包含 $M$ 个整数，分别表示已拥有的种子类型 $K_j$ ， $K_j$ 两两不同。

第 $4$ 至 $K + 3$ 行，每行包含 $3$ 个整数 $A, B, C$ ，表示第 $A$ 类作物和第 $B$ 类作物杂交可以获得第 $C$ 类作物的种子。

输出格式

输出一个整数，表示得到目标种子的最短杂交时间。

样例解释

$1 \le N \le 2000$ ,
$2 \le M \le N$ ,
$1 \le K \le 10^5$ ,
$1 \le T \le N$ ,
$1 \le T_i \le 100$ ,
$1 \le K_j \le M$ ,
保证目标种子一定可以通过杂交得到。
不保证作物 $A$ 和 $B$ 杂交只能生成作物 $C$ （也就是说， $A × B → C$ 和 $A × B → D$ 可能同时在输入中出现）
不保证作物 $C$ 只能由作物 $A$ 和 $B$ 杂交生成（也就是说， $A × B → D$ 和 $A × C → D$ 可能同时在输入中出现）。
不保证同一杂交公式不在输入中重复出现。

输入样例：

6 2 4 6
5 3 4 6 4 9
1 2
1 2 3
1 3 4
2 3 5
4 5 6

输出样例：

16

样例解释

第 $1$ 天至第 $5$ 天，将编号 $1$ 与编号 $2$ 的作物杂交，得到编号 $3$ 的作物种子。

第 $6$ 天至第 $10$ 天，将编号 $1$ 与编号 $3$ 的作物杂交，得到编号 $4$ 的作物种子。

第 $6$ 天至第 $9$ 天，将编号 $2$ 与编号 $3$ 的作物杂交，得到编号 $5$ 的作物种子。

第 $11$ 天至第 $16$ 天，将编号 $4$ 与编号 $5$ 的作物杂交，得到编号 $6$ 的作物种子。

总共花费 $16$ 天。

解题

方法一：动态规划 SPFA算法

思路

本题是用 Bellman-Ford 的本质——动态规划来思考，而因为 SPFA 算法是 Bellman-Ford 算法的宽搜优化，所以可以用 SPFA 算法进行优化。

思维过程：

状态转移方程：$f(i, j) = \min(f(i, j), \max(f(i-1, x), f(i-1, y)) + \max(T_x, T_y))$ 。

按照该状态表示， $f(n-1, t)$ 就是答案（得到目标种子的最短杂交时间），因为从初始种子迭代到目标种子最多只会经过 $n-1$ 条边。

时间复杂度：$O(NK)$ ，按照本题的数据范围是 $O(2 \times 10^8)$ ，显然会超时，但是加一个小优化就可以过 ：如果在某一次迭代中 没有任何作物的最小花费时间被更新 ，那就说明已经找到了最优解。

另外也可以使用 SPFA 算法进行优化，首先因为状态都是从上一层转移过来的，所以动归中第一维的 $i$ 可以直接被优化掉，其次观察状态转移方程发现：每次只有在 $f(x)$ 或者 $f(y)$ 发生变化后 $f(j)$ 才有可能被更新，所以可以直接利用 SPFA算法进行宽搜优化。

代码

Bellman-Ford 算法 + 优化

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n, m, k, t;
    static int[] times, init;
    static int[][] edges;
    
    static int bellmanFord(int dest) {
        int[] dists = new int[n + 1];
        Arrays.fill(dists, INF);
        // 一开始就有的作物不需要花时间
        for (int u : init) dists[u] = 0;
        for (int i = 0; i < n - 1; ++i) {
            int[] prev = dists.clone(); // 备份 防止更新串联
            boolean flag = false;
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], p = edge[2];
                int cost = Math.max(prev[u], prev[v]) + Math.max(times[u], times[v]);
                // 松弛操作
                if (cost < dists[p]) {
                    dists[p] = cost;
                    flag = true;
                }
            }
            // 如果本次迭代中没有
            if (!flag) break;
        }
        return dists[dest];
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        in.nextToken();
        k = (int) in.nval;
        in.nextToken();
        t = (int) in.nval;
        times = new int[n + 1];
        init = new int[m];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            times[i] = (int) in.nval;
        }
        while (m-- > 0) {
            in.nextToken();
            init[m] = (int) in.nval;
        }
        edges = new int[k][3];
        for (int i = 0; i < k; ++i) {
            in.nextToken();
            edges[i][0] = (int) in.nval;
            in.nextToken();
            edges[i][1] = (int) in.nval;
            in.nextToken();
            edges[i][2] = (int) in.nval;
        }
        System.out.println(bellmanFord(t));
    }
}

SPFA 算法

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n, m, k, t;
    // times: 每个点的种植时间  init: 初始已经有了的点
    static int[] times, init;
    static int[] h, another, product, ne;
    static int idx;
    
    // 本题加边加的并不是传统边的概念  而是相当于是用单链表记录a可以和b一起杂交成c
    static void add(int a, int b, int c) {
        another[idx] = b;
        product[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    static int spfa(int dest) {
        int[] dists = new int[n + 1]; // 最短路数组 这里表示最小花费时间
        boolean[] has = new boolean[n + 1];
        Queue<Integer> que = new LinkedList<>();
        Arrays.fill(dists, INF);
        // 把所有初始就有的作物加入到队列当中
        for (int u : init) {
            dists[u] = 0;
            que.offer(u);
            has[u] = true;
        }
        while (!que.isEmpty()) {
            int u = que.poll();
            has[u] = false;
            for (int i = h[u]; i != -1; i = ne[i]) {
                // u + v -> p
                int v = another[i], p = product[i];
                int cost = Math.max(dists[u], dists[v]) + Math.max(times[u], times[v]);
                if (cost < dists[p]) {
                    dists[p] = cost;
                    // 如果原材料有更新 产物就有机会被更新
                    if (!has[p]) {
                        que.offer(p);
                        has[p] = true;
                    }
                }
            }
        }
        return dists[dest];
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        in.nextToken();
        k = (int) in.nval;
        in.nextToken();
        t = (int) in.nval;
        times = new int[n + 1];
        init = new int[m];
        h = new int[n + 1];
        Arrays.fill(h, -1);
        another = new int[k * 2];
        product = new int[k * 2];
        ne = new int[k * 2];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            times[i] = (int) in.nval;
        }
        while (m-- > 0) {
            in.nextToken();
            init[m] = (int) in.nval;
        }
        while (k-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            in.nextToken();
            int c = (int) in.nval;
            add(a, b, c); // 对于a来说它可以和b杂交出c
            add(b, a, c); // 对于b来说它也可以和a杂交出c
        }
        System.out.println(spfa(t));
    }
}