【题意】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 }
原文：http://www.cnblogs.com/KonjakJuruo/p/5971312.html