LG P1875 佳佳的魔法药水 题解

· · 题解

思路

我们可以从 DP 的角度来考虑这道题。

设 f[c] 代表药品 C 需要的最小花费，我们可以写出状态转移方程：f[c]=\min(w[c],f[a]+f[b])，简单分析后就可以发现，状态与状态之间可能会存在环形的依赖关系（即不是一张 DAG，没有直接的拓扑序来供我们转移）。

通常情况下，在“图状”的 DP 时，遇到环形依赖，有两个解决办法：

本题两种方法都能做，但大部分题解都用的是 Dijkstra，所以这里我们采用 SPFA 来进行迭代求解。

先解决最小值怎么求：

我们将药水抽象为点，将“1 份 A 药水混合 1 份 B 药水就可以得到 1 份 C 药水”抽象为“C 有一组边能达到它的边，分别为 A 到 C 和 B 到 C”，然后枚举更新时按照组的单位来更新。

每个点都有个基础状态，即花费为 w[i] 的状态，由于我们不知道从哪个点开始更新最好，所以我们把所有点都入队。

对于每个点，枚举能到达它的边（以组为单位），计算当前点 u 是否能被更新，如果点 u 能被更新，说明药水 u 的最小花费变小了，所以所有以药水 u 为原料的药水的花费都可能变小，所以都要入队。

这样就能得到 0 号药水的最小花费，我们再来考虑怎么样计算最短路径的条数：

可能有人会有疑问，为什么不在计算最短路的同时记录最短路的条数呢？因为那种记录最短路的条数的思想也是基于 DP 的思想，只有在拓扑序下转移才能被正确的求出来，然而 SPFA 不是按照拓扑序进行转移的。

我们可以采用记忆化搜索的方式进行计算，因为整个最短路径的 DAG 图已经被构造出来了，递归回去计算就行。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1000001;
int n, cnt = 0;
int f[N], head[N], w[N], tot[N];
bool vis[N];

struct Edge {
    int a, b, next;
};
Edge e[M];
vector<int> belongs[N];

void add(int a, int b, int v) {
    e[++cnt] = {a, b, head[v]};
    head[v] = cnt;
}

void spfa() {
    queue<int> q;
    // 将每个点入队
    for (int i = 0; i <= n - 1; i++) {
        q.push(i);
        f[i] = w[i];
        vis[i] = 1;
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i != -1; i = e[i].next) {
            // 枚举每组边
            int a = e[i].a, b = e[i].b;
            if (f[u] > f[a] + f[b]) {
                f[u] = f[a] + f[b];
                // 如果药水u的花费能够降低，那么由药水u合成出来的药水的花费都有可能降低
                // 所以要把这些点都放回队列里
                for (auto v: belongs[u])
                    if (vis[v] == 0)
                        vis[v] = 1, q.push(v);
            }
        }
    }
}

int dfs(int u) {
    if (tot[u] != 0) return tot[u];
    if (f[u] == w[u]) tot[u]++;
    for (int i = head[u]; i != -1; i = e[i].next) {
        int a = e[i].a, b = e[i].b;
        if (f[u] == f[a] + f[b]) {
            tot[a] = dfs(a);
            tot[b] = dfs(b);
            tot[u] += tot[a] * tot[b];
        }
    }
    return tot[u];
}

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    cin >> n;

    for (int i = 0; i < n; i++) cin >> w[i], head[i] = -1;
    int a, b, c;
    while (cin >> a >> b >> c) {
        add(a, b, c);
        if (a == b) continue;
        // 这里记录a和b分别能合成哪些药水，等会儿状态更新时会用到
        belongs[a].push_back(c);
        belongs[b].push_back(c);
    }
    spfa();
    dfs(0);
    cout << f[0] << " " << tot[0] << endl;
    return 0;
}

总结