AcWing 324. 贿赂FIPA

2021-03-17 20:23

阅读：482

标签：二维 ace problem als next ipa string line 计划

题目链接

大型补档计划

\(f[i][j]\) 表示第 \(i\) 个国家，获得 \(j\) 个国家支持，用的最少花费

\(f[i][0] = 0\)
\(f[i][sz[i]] = w[i]\)

对于每条边 \((u, v)\)
枚举 \(u\) 的第二维 \(j\)，\(v\) 的第二维 \(k\) \((k
\(f[u][j] = min(f[u][j], f[v][k] + f[u][j - k])\)

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 205;
int n, m;
int head[N], numE = 0, out[N], idx = 1;
map 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 = 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 > 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

AcWing 324. 贿赂FIPA

标签：二维 ace problem als next ipa string line 计划

原文地址：https://www.cnblogs.com/dmoransky/p/12380439.html

上一篇：Z390上安装Win10与Win7

下一篇：C#开发: 准备工作-C# 新建工程

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 324. 贿赂FIPA
文章链接：http://soscw.com/essay/65452.html

亲，登录后才可以留言！

AcWing 324. 贿赂FIPA

评论

热门文章

推荐文章

最新文章

置顶文章