首页 > 代码库 > 【hdu3080】01背包(容量10^7)

【hdu3080】01背包(容量10^7)

【题意】n个物品,有wi和vi,组成若干个联通块,只能选取一个联通块,问得到m的价值时最小要多少空间(v)。n<=50,v<=10^7

【题解】

先用并查集找出各个联通块。

这题主要就是v太大了,跟以往的背包不同。

我们回想01背包,f[j+v[i]]=max(f[j]+w[i]);

在这里面很明显很多状态都没有用。

优化:如果有2个状态,v1<=v2 && w1>=w2 则(v2,w2)这个状态是没有用的。

我们回到滚动数组中:

f[i][j+v[i]]=max(f[i^1][j]+w[i]);

那么我们可以用两个优先队列,q0存以前的f[i-1],q1存当前的f[i]。

我们在求f[i]的时候,就把q0一个个pop出来,更新后放到q1里面去。

做完i,我们要把q1放到q0,然后做i+1。

在把q1放到q0的时候就把没用的状态去掉(对于(v,val),先按val从大到小排序,再按v从小到大排序,对同样的val取最小的v)。

 

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<vector>
 8 using namespace std;
 9 
10 typedef long long LL;
11 const LL N=60,INF=(LL)1e15;
12 LL n,m,fa[N],t[N],w[N],c[N][N];
13 struct node{LL v,val;};
14 
15 struct cmp
16 {
17     bool operator () (node &x,node &y)
18     {
19         if(x.val==y.val) return x.v<y.v;
20         return x.val<y.val;
21     }
22 };
23 
24 priority_queue<node,vector<node>,cmp> q0,q1;
25 
26 LL findfa(LL x)
27 {
28     if(fa[x]==x) return x;
29     return findfa(fa[x]);
30 }
31 
32 LL minn(LL x,LL y){return x<y ? x:y;}
33 
34 int main()
35 {
36     freopen("a.in","r",stdin);
37     freopen("me.out","w",stdout);
38     int T,cas=0;
39     scanf("%d",&T);
40     while(T--)
41     {
42         scanf("%d%d",&n,&m);
43         for(int i=1;i<=n;i++) fa[i]=i;
44         for(int i=1;i<=n;i++)
45         {
46             int num,xx;
47             scanf("%lld%lld%d",&t[i],&w[i],&num);
48             for(int j=1;j<=num;j++)
49             {
50                 scanf("%d",&xx);
51                 fa[findfa(i)]=findfa(xx);
52             }
53         }
54         memset(c,0,sizeof(c));
55         for(int i=1;i<=n;i++)
56         {
57             fa[i]=findfa(i);
58             c[fa[i]][++c[fa[i]][0]]=i;
59         }
60         node x,p,f;
61         LL ans=INF;
62         for(int k=1;k<=n;k++) if(c[k][0])
63         {
64             // printf("k = %d\n",k);
65             while(!q0.empty()) q0.pop();
66             while(!q1.empty()) q1.pop();
67             x.v=0;x.val=0;
68             q0.push(x);
69             for(int j=1;j<=c[k][0];j++)
70             {
71                 int i=c[k][j];
72                 while(!q0.empty())
73                 {
74                     x=q0.top();q0.pop();q1.push(x);
75                     f.v=x.v+t[i];
76                     f.val=x.val+w[i];
77                     if(f.v>=ans) continue;
78                     if(f.val>=m) {ans=minn(ans,f.v);continue;}
79                     q1.push(f);
80                 }
81                 LL mn=INF;
82                 while(!q1.empty()) 
83                 {
84                     x=q1.top();q1.pop();
85                     if(x.val>=m) ans=minn(ans,x.v);
86                     if(x.v<mn) mn=x.v,q0.push(x);
87                     // printf("v = %lld  val = %lld\n",x.v,x.val);
88                 }
89             }
90             // f[i^1][v+c[i]]=maxx(f[i^1][v+c[i]],f[i][v]+w[i]]);
91         }
92         if(ans<INF) printf("Case %d: %lld\n",++cas,ans);
93         else printf("Case %d: Poor Magina, you can‘t save the world all the time!\n",++cas);
94     }
95     return 0;
96 }

 

【hdu3080】01背包(容量10^7)