[蓝桥杯 2024 国 Python B] 工厂

· · 题解

拓扑排序做法。

注意到：x\le y，若不考虑 x=y，则建边 (x,y,k,w) 的图一定是一个 DAG（有向无环图）。

考虑最后售卖的物品，容易发现：最终卖出去的一定只是某一个物品，不会卖出多个物品。简单理解就是因为要求性价比最大，那么多个物品的性价比加起来一定不会超过这些物品中性价比最大的那个（糖水不等式）。

且工人的生产决策只与数量相关，与物品价格无关，所以只需要考虑数量和工人数之比。

所以，在 DAG 上 dp 即可：dp[x] 表示只售卖 x 这个物品的最大性价比：\frac{p}{q}，实际意义为：q 个工人生产 p 个物品 x。

那么转移边 (x,y,k,w) 时，易得：dp[x]=\dfrac{p}{q},\dfrac{\frac{\text{lcm}(p,k)}{k}\times w}{q\times\frac{\text{lcm}(p,k)}{p}+\frac{\text{lcm}(p,k)}{k}}\rightarrow dp[y]。

注意：此处分数不能约分，因为分母表示的是工人数量，具有实际意义。因为题目限制了 k\le 10，所以此处反复取 \text{lcm} 并不会爆炸。

最后再考虑 x=y 的情况，事实上，因为 x=y 时生成的物品是自己，所以可以先保留 \dfrac{w}{k} 最大的那一组，然后在 dp 过程中，dp[x] 的值更新完后，对自己进行一次 (x,x,k,w) 的转移即可。

因为具体实现中的 \text{lcm} 只和 k\le 10 进行，所以这一步时间复杂度可以近似看成 O(1)（或是进行一次辗转相除后，预处理 10 范围内的所有 \gcd 即可）。

DAG 上 dp 采用拓扑排序实现，时间复杂度：O(n)。

from collections import deque
from math import *

n, m = map(int, input().split())

a = list(map(int, input().split()))

x = [0 for _ in range(m)]
y = [0 for _ in range(m)]
k = [0 for _ in range(m)]
w = [0 for _ in range(m)]

p = [[] for _ in range(n)]
deg = [0 for _ in range(n)]

def add(x, y, k, w):
    p[x].append([y, k, w])
    deg[y] += 1

dp = [[0,1] for _ in range(n)]

def max(x, y):
    if x[0] * y[1] > y[0] * x[1]:
        return x
    return y

b = [[0, 1] for _ in range(n)]

for i in range(m):
    x[i], y[i], k[i], w[i] = map(int, input().split())
    x[i] -= 1
    y[i] -= 1
    if k[i] == 0:
        dp[y[i]] = max(dp[y[i]], [w[i], 1])
    else: 
        if x[i] == y[i]:
            b[x[i]] = max(b[x[i]], [w[i], k[i]])
        else:
            add(x[i], y[i], k[i], w[i])

q = deque()

for i in range(n):
    if not deg[i]:
        q.append(i)

while q:
    now = q.popleft()
    if b[now][0] and dp[now][0]:
        b[now][0], b[now][1] = b[now][1], b[now][0]

        fz = b[now][1] * lcm(dp[now][0], b[now][0]) // b[now][0]
        fm = dp[now][1] * lcm(dp[now][0], b[now][0]) // dp[now][0]
        fm = fm + lcm(dp[now][0], b[now][0]) // b[now][0]

        dp[now] = max(dp[now], [fz, fm])
    for v in p[now]:
        fz, fm = 0, 1
        if dp[now][0] != 0:
            fz = v[2] * lcm(dp[now][0], v[1]) // v[1]
            fm = dp[now][1] * lcm(dp[now][0], v[1]) // dp[now][0]
            fm = fm + lcm(dp[now][0], v[1]) // v[1]
        dp[v[0]] = max(dp[v[0]], [fz, fm])
        deg[v[0]] -= 1
        if not deg[v[0]]:
            q.append(v[0])

ans = [0, 1]
for i in range(n):
    dp[i][0] *= a[i]
    ans = max(ans, dp[i])

res = ans[0] / ans[1]
print(f"{res:.2f}")