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;
}