POJ3345 / UVA1222 Bribing FIPA

发布于 2019-11-01  287 次阅读


Vjudge

推荐先做Luogu2014

背包类树形DP入门题,语言NOI题(输入就是傻逼

考虑树形DP,设f[u][i]表示以u为根节点的子树,收买i个国家的最小代价。

根据题意,有些国家可能只是其他国家的老大,按照这个状态进行DP可以先建立一个0作为这个森林新树根,将原森林中每棵树的树根连到这个点上,就可以DP

转移很简单,写成公式太麻烦,详见代码

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 200 + 5;

int n, m;
int w[SIZE], fa[SIZE], s[SIZE], f[SIZE][SIZE];

std::map < string, int > serial;
std::vector < int > son[SIZE];

inline void DFS(int u)
{
    f[u][0] = 0, s[u] = 1;
    for (int i = 0; i < son[u].size(); i++) {
        int v = son[u][i];
        DFS(v);
        s[u] += s[v];
        for (int j = n; j >= 0; j--) {
            for (int k = 0; k <= j; k++) {
                f[u][j] = std::min(f[u][j], f[u][j - k] + f[v][k]);
            }
        }
    }
    f[u][s[u]] = std::min(f[u][s[u]], w[u]);
    return;
}   

inline void init()
{
    for (int i = 0; i <= n; i++) son[i].clear();
    serial.clear();
    memset(fa, 0, sizeof(fa)); memset(w, 0, sizeof(w));
    memset(s, 0, sizeof(s)); memset(f, 0x3f, sizeof(f));
}

int main()
{
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    char in[SIZE];
    while (fgets(in, 200, stdin)) {
        if (in[0] == '#') break;
        sscanf(in, "%d%d", &n, &m);
        init();
        int cnt = 0, ans = 2e9;
        string str, s;
        for (int i = 1; i <= n; i++) {
            std::cin >> str;
            if (!serial.count(str)) serial[str] = ++cnt;
            scanf("%d", &w[serial[str]]);
            while (getchar() != '\n') {
                std::cin >> s;
                if (!serial.count(s)) serial[s] = ++cnt;
                son[serial[str]].push_back(serial[s]);
                fa[serial[s]] = 1;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!fa[i]) son[0].push_back(i);
        }
        w[0] = 2e9;
        DFS(0);
        for (int i = m; i <= n; i++) {
            ans = std::min(ans, f[0][i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

朴实沉毅