重题
有 \(n\) 个物品，每个物品有价格 \(c_i\) 和所需个数 \(k_i\) ，所有物品必须恰好买 \(k_i\) 个。有 \(m\) 种优惠方案给出 \(x,\ y,\ w\) ：若买过至少一件 \(x\) 物品，则 \(y\) 物品只需 \(w\) 的价格 \((w<c_y)\) ，数据中所有 \((x,\ y)\) 不同且 \(x\neq y\) 。求最少花费。所有数据保留两位小数。
\(1\leq n\leq50,\ 0<c_i\leq1000,\ 0\leq k\leq100\)
最小树形图
首先判掉无效的 \(k_i=0\) 的物品，发现如果每种物品都买过一遍，那么随后所有的商品都可以以最低价格购买。那么如何求每种物品各买一个的最小花费呢？可以将 \(m\) 种优惠方案看做树边，再加一个虚拟节点 \(n+1\) ，连边 \((n+1,\ i,\ c_i)\) ，接着跑最小树形图就可以解决了
因为 \(m\) 是 \(n^2\)级别的，所以时间复杂度 \(O(n^3)\)
代码
#includeusing namespace std;typedef double db;const int maxn = 60;int n, m, mp[maxn], sum[maxn], pre[maxn], vis[maxn], tid[maxn]; db ans, a[maxn], val[maxn];struct edges { int u, v; db w;} e[maxn * maxn];db edmonds() { int rt = n; while (1) { memset(tid, 0, sizeof tid); memset(vis, 0, sizeof vis); for (int i = 1; i <= n; i++) { val[i] = 1e9; } 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; } } int tot = 0; for (int i = 1; i < n; i++) { int u = i; ans += val[i]; while (vis[u] != i && !tid[u] && u != rt) { vis[u] = i, u = pre[u]; } if (!tid[u] && u != rt) { 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]; } rt = tid[rt], n = tot; } return ans;}int main() { int t1, t2; scanf("%d", &t1); for (int i = 1; i <= t1; i++) { db x; int y; scanf("%lf %d", &x, &y); if (y) mp[i] = ++n, a[n] = x, sum[n] = y; } scanf("%d", &t2); m = n + t2, n++; for (int i = 1; i < n; i++) { e[t2 + i].u = n, e[t2 + i].v = i, e[t2 + i].w = a[i]; } for (int i = 1; i <= t2; i++) { int u, v; db w; scanf("%d %d %lf", &u, &v, &w); u = mp[u], v = mp[v]; if (!u || !v) continue; a[v] = min(a[v], w); e[i].u = u, e[i].v = v, e[i].w = w; } for (int i = 1; i <= n; i++) { ans += a[i] * (sum[i] ? sum[i] - 1 : 0); } printf("%.2f", edmonds()); return 0;}