HDU6007-Mr. Panda and Crystal(最短路+完全背包)

题目链接:HDU6007-Mr. Panda and Crystal

题意:

魔法师最开始有m的魔力,然后有n种宝石,有些宝石可以直接花费一定的魔力创造出来,有些宝石不能直接创造,然后有k个合成公式,可以合成不同的宝石,每种宝石都有一定的价格,问最多能获利多少。

题解:

可以先预处理出得到每一个宝石的最小代价,然后进行完全背包即可。

预处理的时候,把每一个合成公式存下来,然后利用最短路进行处理,处理到新的一个点的时候,遍历所有可以合成该宝石的公式,更新点权。

预处理结束后,把魔力作为背包容量,然后进群作为收益。做完全背包。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 10;
const int MAXM = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int T, m, n, k;
struct EDGE
{
    int v, nxt;
    ll w;
} edge[MAXM];
int ecnt = 0, fir[maxn];
void addedge(int u, int v, ll w)
{
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
int cost[200 + 10], val[200 + 10], tot[200 + 10];
ll dis[maxn];
bool used[maxn];
int dp[10005];
vector<pair<int, pair<int, int>>> F[200 + 10];
void dijkstra(int st)
{
    priority_queue<pair<ll, int>> que;
    while (!que.empty())
        que.pop();
    for (int i = 1; i <= n; i++)
        dis[i] = m + 1;
    memset(used, 0, sizeof(used));
    for (int i = 1; i <= n; i++)
        if (cost[i] > 0)
        {
            dis[i] = cost[i];
            que.push({-dis[i], i});
        }
    while (!que.empty())
    {
        int u = que.top().second;
        que.pop();
        if (used[u])
            continue;
        used[u] = 1;
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            int temp = inf, sum = 1, tmp = 0;
            if (used[v])
                continue;
            for (auto x : F[v])
            {
                if (x.first != sum)
                {
                    sum++;
                    temp = min(temp, tmp);
                    tmp = 0;
                }
                tmp += dis[x.second.first] * x.second.second;
            }
            temp = min(temp, tmp);
            if (dis[v] > temp)
            {
                dis[v] = temp;
                que.push({-dis[v], v});
            }
        }
    }
}
int main()
{
    scanf("%d", &T);
    int icase = 0;
    while (T--)
    {
        memset(dp, 0, sizeof(dp));
        scanf("%d%d%d", &m, &n, &k);
        memset(cost, 0, sizeof(cost));
        memset(fir, -1, sizeof(fir));
        memset(tot, 0, sizeof(tot));
        ecnt = 0;
        for (int i = 1; i <= n; i++)
        {
            F[i].clear();
            int op;
            scanf("%d", &op);
            if (op)
            {
                scanf("%d%d", &cost[i], &val[i]);
                addedge(0, i, 0);
            }
            else
                scanf("%d", &val[i]);
        }
        for (int i = 1; i <= k; i++)
        {
            int v, num;
            scanf("%d", &v);
            scanf("%d", &num);
            int x, y;
            for (int j = 1; j <= num; j++)
            {
                scanf("%d%d", &x, &y);
                addedge(x, v, 0);
                if (j == 1)
                    F[v].push_back({++tot[v], {x, y}});
                else
                    F[v].push_back({tot[v], {x, y}});
            }
        }
        dijkstra(0);
        for (int i = 1; i <= n; i++)
        {
            dis[i] = min((int)dis[i], m + 1);
        }
        for (int i = 1; i <= n; i++)
        {
            for (int v = (int)dis[i]; v <= m; v++)
            {
                if (dis[i] != m + 1)
                    dp[v] = max(dp[v], dp[v - dis[i]] + val[i]);
            }
        }
        printf("Case #%d: %d\n", ++icase, dp[m]);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。