欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-22 11:38:33
...

题目链接

思路:先求出每个道具的最小造价,再跑完全背包即可。

我们不停的用 当前已得最小造价的道具来更新当前道具可以合成的道具,类似于dij求最短路那样。就能获得每个道具的最小花费了。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
int t,m,n,k,cas;
int st[N];
int a[N],b[N];
int dp[10005];
struct uzi{
  int a;
  vector<pair<int,int>>v;
  bool sta;
  int pos;
}p[N];
vector<int>v[N];
int main() {
  ios::sync_with_stdio(false);
  for(cin>>t,cas=1;cas<=t;cas++){
    cin>>m>>n>>k;memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
      v[i].clear();
      cin>>st[i];
      if(st[i]){
        cin>>a[i]>>b[i];
      }else{
        cin>>b[i];
        a[i]=1e9;
      }
    }
    priority_queue<pair<LL,int > >Q;
    vector<uzi>res;
    for(int i=1;i<=k;i++){
      int x,y;
      cin>>x>>y;
      vector<pair<int,int> >QQ;
      for(int j=1;j<=y;j++){
        int e,f;
        cin>>e>>f;
        v[e].pb(i);
        QQ.pb({e,f});
      }
      p[i]= {x,QQ,0,i};
      res.pb(p[i]);
    }
    auto get=[&](vector<pair<int,int>>&v){
      LL tot=0;
      for(auto ka:v){
        tot+=1ll*ka.se*a[ka.fi];
      }
      return tot;
    };
    for(int i=1;i<=n;i++){
      if(st[i]){
        Q.push({-a[i],i});
      }
    }
    while(!Q.empty()){
      auto x=Q.top();
      Q.pop();
      for(auto ka:v[x.se]){
        LL tmp=get(p[ka].v);
        if(a[p[ka].a]>tmp){
          a[p[ka].a]=tmp;
          Q.push({-a[p[ka].a],p[ka].a});
        }
      }
    }
    for(int i=1;i<=n;i++){
      for(int j=a[i];j<=m;j++){
        dp[j]=max(dp[j],dp[j-a[i]]+(int)b[i]);
      }
    }
    cout<<"Case #"<<cas<<": "<<dp[m]<<'\n';
  }
  return 0;
}