【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）。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long LL;

 const LL N=,INF=(LL)1e15;

 LL n,m,fa[N],t[N],w[N],c[N][N];

 struct node{LL v,val;};

 struct cmp

 {

     bool operator () (node &x,node &y)

     {

         if(x.val==y.val) return x.v<y.v;

         return x.val<y.val;

     }

 };

 priority_queue<node,vector<node>,cmp> q0,q1;

 LL findfa(LL x)

 {

     if(fa[x]==x) return x;

     return findfa(fa[x]);

 }

 LL minn(LL x,LL y){return x<y ? x:y;}

 int main()

 {

     freopen("a.in","r",stdin);

     freopen("me.out","w",stdout);

     int T,cas=;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++) fa[i]=i;

         for(int i=;i<=n;i++)

         {

             int num,xx;

             scanf("%lld%lld%d",&t[i],&w[i],&num);

             for(int j=;j<=num;j++)

             {

                 scanf("%d",&xx);

                 fa[findfa(i)]=findfa(xx);

             }

         }

         memset(c,,sizeof(c));

         for(int i=;i<=n;i++)

         {

             fa[i]=findfa(i);

             c[fa[i]][++c[fa[i]][]]=i;

         }

         node x,p,f;

         LL ans=INF;

         for(int k=;k<=n;k++) if(c[k][])

         {

             // printf("k = %d\n",k);

             while(!q0.empty()) q0.pop();

             while(!q1.empty()) q1.pop();

             x.v=;x.val=;

             q0.push(x);

             for(int j=;j<=c[k][];j++)

             {

                 int i=c[k][j];

                 while(!q0.empty())

                 {

                     x=q0.top();q0.pop();q1.push(x);

                     f.v=x.v+t[i];

                     f.val=x.val+w[i];

                     if(f.v>=ans) continue;

                     if(f.val>=m) {ans=minn(ans,f.v);continue;}

                     q1.push(f);

                 }

                 LL mn=INF;

                 while(!q1.empty())

                 {

                     x=q1.top();q1.pop();

                     if(x.val>=m) ans=minn(ans,x.v);

                     if(x.v<mn) mn=x.v,q0.push(x);

                     // printf("v = %lld  val = %lld\n",x.v,x.val);

                 }

             }

             // f[i^1][v+c[i]]=maxx(f[i^1][v+c[i]],f[i][v]+w[i]]);

         }

         if(ans<INF) printf("Case %d: %lld\n",++cas,ans);

         else printf("Case %d: Poor Magina, you can't save the world all the time!\n",++cas);

     }

     return ;

 }