题目

{% fold 点击显/隐题目 %}

Long long time ago, there is a magic continent far far away.

There are N types of magic crystals that contain ancient magic powers. Each of the type of magic crystal has its own price for one piece in the market. As the most powerful magician, Mr. Panda could synthesize some types of crystals by collecting some amount of other types of crystals. He could also create some types of crystals by using some number of his magic powers.

Now, Mr Panda can create any number of crystals as he wish by using no more than M magic powers. He want to know the maximum amount of money he can make by sell all the crytals he creates and synthesizes.

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case starts with 3 positive intergers, M, N and K represent the amount of magic powers Mr. Panda had, the number of crystal types on the magic continent and the number of crystal synthesis equations.

Then N lines follows, each of them starts with one 0 or 1 which indicates whehter Mr. Panda could create this type of crystal.

If the ithi^{th} line starts with 0, which means Mr. Panda couldn’t create crystal type i. Then there is one integer p_ip\_i in this line which is the price for each piece of crystal type i.

If the ithi^{th} line starts with 1, which means Mr. Panda could create crystal type i. Then there are two positive integers c_ic\_i and p_ip\_i in this line, the first is the amout of magic power cost when creates one piece of crystal type i, and the second is is the price for each piece of crystal type i.

The following K lines each start with two interger x_ix\_i and y_iy\_i , which means for synthesizing one piece of crystal type x_ix\_i , y_iy\_i rules should be satisfied. Then there are y_iy\_i pair of positive intergers u_ju\_j and v_jv\_j means for one piece of xth_ix^{th}\_{i} type cristal, we have to collect v_iv\_i piece of crystal type u_iu\_i. Only when all the rules of u_iu\_i and v_iv\_i are satisfied, Mr. Panda could synthesize one piece xth_ix^{th}\_{i} type cristal.

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the maximum amout of money Mr. Panda could make.

limits
● 1≤T≤100.1 ≤ T ≤ 100.
● 1≤M≤10000.1 ≤ M ≤ 10000.
● 1≤N≤200.1 ≤ N ≤ 200.
● 1≤K≤200.1 ≤ K ≤ 200.
● 1≤xi,uj≤N.1 ≤ x_i, u_j ≤ N.
● for each crystal synthesis equation, all uj are different.
● 1≤vj≤100.1 ≤ v_j ≤ 100.
● 1≤ci,pi≤10000.1 ≤ c_i , p_i ≤ 10000.

2 100 3 2 0 20 1 15 10 1 2 1 1 2 2 1 3 1 2 1 3 2 100 3 2 1 3 1 1 4 1 0 10 3 1 1 3 3 1 2 2
Case #1: 330 Case #2: 121
{% endfold %}

题解

有一个有M点魔法值的*膜*魔法师,有n种不同的魔法物品,制造需要c[i]点魔法值,卖出去能获得p[i]元(有一些物品魔法师不会合成)
现在有k种合成法则,可以将y种元素按照v个u元素融合的规则合成x元素
求魔法师最多能卖出去多少钱

如果不考虑最后的合成法则,就是一个标准的完全背包

然后看合成法则部分
通常来说这里可以看成有向图求最短路
这里用模拟的思路来解决

我们每一次都对k种合成法则进行计算,计算合成出来的x的花费是否比之前的少,如果更少就更新
检查完k次后,如果有更新,就说明有可能还能更优,就继续检查,否则就说明是最优结果了
然后就可以背包了
(具体看代码,就几行,看代码更容易理解)

代码

{% fold 点击显/隐代码 %}```cpp Mr. Panda and Crystal https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
using namespace std;

typedef pair<int, int> Pair;
const int maxn = 205;
const int INF = 0x3f3f3f;

int p[maxn];
int c[maxn];
int x[maxn];
vector hc[maxn];
int dp[10005];

int main() {
int T;
scanf("%d", &T);
for(int kase= 1;kase<=T;++kase) {
int n, m, k;
scanf("%d%d%d", &m, &n, &k);

    for (int i = 0; i < k; ++i)
        hc[i].clear();

    for (int i = 1; i <= n; ++i) {
        int t;
        scanf("%d", &t);
        if (t == 0) {
            c[i] = INF;
            scanf("%d", &p[i]);
        } else {
            scanf("%d%d", &c[i], &p[i]);
        }
    }

    for (int i = 0; i < k; ++i) {
        int y;
        scanf("%d%d", &x[i], &y);
        for (int j = 0; j < y; ++j) {
            int u, v;
            scanf("%d%d", &u, &v);
            hc[i].push_back(make_pair(u, v));
        }
    }

    bool change = true;
    while (change) {
        change = false;
        for (int i = 0; i < k; ++i) {
            int cost = 0;
            for (auto iter : hc[i])
                cost += c[iter.first] * iter.second;
            if (cost < c[x[i]]) {
                c[x[i]] = cost;
                change = true;
            }
        }
    }

    // for (int i = 1; i <= n; ++i)
    //     printf("%d : %d %d\n", i, c[i], p[i]);

    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; ++i)
        for (int j = c[i]; j <= m; ++j)
            dp[j] = max(dp[j], dp[j - c[i]] + p[i]);

    int ans = 0;
    for (int i = 1; i <= m; ++i) {
        // printf("dp[%d] = %d\n",i,dp[i]);
        ans = max(dp[i], ans);
    }
    printf("Case #%d: %d\n", kase,ans);
}
return 0;

}

{% endfold %}