大型补档计划
\(f[i][j]\) 表示第 \(i\) 个国家，获得 \(j\) 个国家支持，用的最少花费
\(f[i][0] = 0\)
\(f[i][sz[i]] = w[i]\)
对于每条边 \((u, v)\)
枚举 \(u\) 的第二维 \(j\)，\(v\) 的第二维 \(k\) \((k <= j)\)
\(f[u][j] = min(f[u][j], f[v][k] + f[u][j - k])\)
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <sstream>
using namespace std;
const int N = 205;
int n, m;
int head[N], numE = 0, out[N], idx = 1;
map<string, int> st;
int sz[N], f[N][N], w[N];
struct E{
int next, v;
} e[N];
void add(int u, int v) {
e[++numE] = (E) { head[u], v };
head[u] = numE;
}
void dfs(int u) {
sz[u] = 1;
f[u][0] = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
dfs(v);
sz[u] += sz[v];
for (int j = m; j >= 1; j--)
for (int k = 1; k <= j; k++)
f[u][j] = min(f[u][j], f[u][j - k] + f[v][k]);
}
f[u][min(sz[u], m)] = min(f[u][min(sz[u], m)], w[u]);
for (int i = m - 1; i >= 1; i--) f[u][i] = min(f[u][i], f[u][i + 1]);
}
int main() {
ios::sync_with_stdio(false);
while (cin >> n >> m) {
numE = 0; idx = 1;
memset(head, 0, sizeof head);
memset(f, 0x3f, sizeof f);
memset(out, 0, sizeof out);
st.clear();
for (int i = 1; i <= n; i++) {
int val; string s, b, c;
cin >> c >> val;
if (!st[c]) st[c] = ++idx;
w[st[c]] = val;
int a = st[c];
getline(cin, s);
stringstream ss(s);
while (ss >> b) {
if (!st[b]) st[b] = ++idx;
add(a, st[b]); out[st[b]]++;
}
}
for (int i = 2; i <= idx; i++) if (!out[i]) add(1, i);
w[1] = 1e9; dfs(1);
cout << f[1][m] << endl;
}
}