最小树形图
首先判掉无效的 \(k_i=0\) 的物品，发现如果每种物品都买过一遍，那么随后所有的商品都可以以最低价格购买。那么如何求每种物品各买一个的最小花费呢？可以将 \(m\) 种优惠方案看做树边，再加一个虚拟节点 \(n+1\) ，连边 \((n+1,\ i,\ c_i)\) ，接着跑最小树形图就可以解决了
因为 \(m\) 是 \(n^2\)级别的，所以时间复杂度 \(O(n^3)\)
代码
#include <bits/stdc++.h>
using 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;
}