Problem I. Mr. Panda and Crystal
程序员文章站
2022-05-22 11:38:27
...
搜索加背包 。
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define pus push_back
vector<pair<int ,int > > de[205][205];
int dej[205];
int be[205];
int bj[205];
int jl[205];
int dp[10005];
int s,n,m;
struct node
{
int z;
int x,y;
} d[2005];
void dfs(int node)
{
if(bj[node]) return ;
be[node]=min(be[node],d[node].x);
bj[node]=1;
for(int j=0;j<dej[node];j++)
{
int ans=10005;
if(de[node][j].size()) ans=0;
for(int i=0;i<de[node][j].size();i++)
{
int x=de[node][j][i].first;
int y=de[node][j][i].second;
dfs(x);
ans+=be[x]*y;
if(ans>s) break;
}
be[node]=min(be[node],ans);
}
}
int main()
{
int t;
//cin>>t;
scanf("%d",&t);
int le=1;
while(t--)
{
//cin>>s>>n>>m;
scanf("%d%d%d",&s,&n,&m);
for(int i=0;i<205;i++)
{
d[i].x=d[i].y=10005;
}
memset(dej,0,sizeof(dej));
memset(be,100,sizeof(be));
memset(bj,0,sizeof(bj));
memset(jl,0,sizeof(jl));
//cout<<be[0]<<endl;
for(int i=0;i<205;i++)
{
for(int j=0;j<205;j++)
{
de[i][j].clear();
}
}
for(int i=1;i<=n;i++)
{
// cin>>d[i].z;
scanf("%d",&d[i].z);
if(d[i].z)
{
//cin>>d[i].x>>d[i].y;
scanf("%d%d",&d[i].x,&d[i].y);
}
else
{
//cin>>d[i].y;
scanf("%d",&d[i].y);
}
be[i]=d[i].x;
}
int x,y;
for(int i=0;i<m;i++)
{
// cin>>x>>y;
scanf("%d%d",&x,&y);
jl[i]=x;
int a,b;
for(int j=0;j<y;j++)
{
//cin>>a>>b;
scanf("%d%d",&a,&b);
de[x][dej[x]].pus(mk(a,b));
}
dej[x]++;
}
for(int i=0;i<m;i++)
dfs(jl[i]);
// for(int i=1;i<=n;i++) cout<<i<<' '<<be[i]<<endl;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
if(be[i]<=s)
for(int j=be[i];j<=s;j++)
{
dp[j]=max(dp[j],dp[j-be[i]]+d[i].y);
}
}
cout<<"Case #"<<le++<<": "<<dp[s]<<endl;
}
}
推荐阅读
-
Codeforces 101206 I & HDU 6007 Mr. Panda and Crystal
-
HDU 6007 - Mr. Panda and Crystal ( 最短路+完全背包 )
-
[HDU - 6007] Mr. Panda and Crystal
-
Hdu 6007 Mr. Panda and Crystal 最短路+完全背包
-
hdu6007 Mr. Panda and Crystal (最短路+完全背包)
-
Problem I. Mr. Panda and Crystal
-
hdu 6007 Mr. Panda and Crystal(最短路+完全背包)
-
HDU 6007 Mr. Panda and Crystal(dijkstra变形+完全背包)