有 \(n\) 个课程，每种课程有 \(a_i\) 级，一开始你每种课程都为 \(0\) 级，有 \(m\) 个升级方案：\((x,\ l1,\ y,\ l2,\ c)\) ，若你课程 \(x\) 已达到 \(l1\) 级，那么你可以花费 \(c\) 的价格，使得课程 \(y\) 达到 \(l2\) 级。求最小花费使得所有课程满级。
\(n\leq50,\ m\leq2\times10^3,\ a_i\leq500\)
最小树形图
将每个课程拆为 \(a_i\) 个点，分别表示此课程等级为 \(0\cdots a_i\) 。建一个虚拟根节点，连向所有等级为 \(0\) 的节点，边权为 \(0\) 。升级方案可以连边课程 \(x\) 的 \(l1\cdots a_x\) 到课程 \(y\) 的 \(l2\) ，边权为 \(c\) ，再从所有等级为 \(k\) 的节点向等级为 \(k-1\) 的节点连边，权值为 \(0\) ，接着跑最小树形图就吼辣
时间复杂度 \(O(m\sum a_i)\)
代码
#includeusing namespace std;const int maxn = 2.5e4 + 10, maxm = 1e6 + 10;int n, m, k, a[60], mp[60][510], val[maxn], vis[maxn], pre[maxn], tid[maxn];struct edges { int u, v, w; edges(int x = 0, int y = 0, int z = 0) : u(x), v(y), w(z) {}} e[maxm];int edmonds() { int ans = 0; while (1) { memset(vis, 0, sizeof vis); memset(tid, 0, sizeof tid); memset(val, 0x3f, sizeof val); for (int i = 1; i <= m; i++) { int u = e[i].u, v = e[i].v; if (u != v && e[i].w < val[v]) { val[v] = e[i].w, pre[v] = u; } } for (int i = 1; i < n; i++) { if (val[i] > 1e9) return -1; } int tot = 0; for (int i = 1; i < n; i++) { int u = i; ans += val[i]; while (u < n && !tid[u] && vis[u] != i) { vis[u] = i, u = pre[u]; } if (u < n && !tid[u]) { tid[u] = ++tot; for (int v = pre[u]; u != v; v = pre[v]) { tid[v] = tot; } } } if (!tot) break; for (int i = 1; i <= n; i++) { if (!tid[i]) tid[i] = ++tot; } for (int i = 1; i <= m; i++) { int u = e[i].u, v = e[i].v; e[i].u = tid[u], e[i].v = tid[v]; if (u != v) e[i].w -= val[v]; } n = tot; } return ans;}void solve() { m = 0; for (int i = 1; i <= n; i++) { scanf("%d", a + i); mp[i][0] = mp[i - 1][a[i - 1]] + 1; for (int j = 1; j <= a[i]; j++) { mp[i][j] = mp[i][j - 1] + 1; e[++m] = edges(mp[i][j], mp[i][j - 1], 0); } } for (int i = 1; i <= k; i++) { int p1, p2, l1, l2, w; scanf("%d %d %d %d %d", &p1, &l1, &p2, &l2, &w); for (int j = l1; j <= a[p1]; j++) { e[++m] = edges(mp[p1][j], mp[p2][l2], w); } } for (int i = 1; i <= n; i++) { e[++m] = edges(mp[n][a[n]] + 1, mp[i][0], 0); } n = mp[n][a[n]] + 1; printf("%d\n", edmonds());}int main() { while (scanf("%d %d", &n, &k) == 2 && n && k) { solve(); } return 0;}