問(wèn)題 B: 小魚(yú)的搭配購(gòu)物
時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB

[提交][狀態(tài)][討論版]
題目描述
小魚(yú)最近特別喜歡口紅，決定去選口紅，商店里有n支口紅，口紅被編號(hào)為1,2，……n，并且每支口紅都有一個(gè)價(jià)值。但是商店老板跟她說(shuō)，一些口紅要搭配來(lái)買才好，所以買一支口紅則與這支口紅有搭配的口紅都要買，但是小魚(yú)的錢(qián)有限，所以她希望買的價(jià)值越多越好。

輸入
第1行n，m，w表示n支口紅，m個(gè)搭配，小魚(yú)有w的錢(qián)。

第2至n+1行，每行ci，di表示 i 支口紅的價(jià)錢(qián)和價(jià)值。

第n+2至n+1+m行，每行 ui、vi 表示買 ui 必須買 vi，同理，如果買 vi 就必須買 ui。

輸出
一行，表示可以獲得的最大價(jià)值。
樣例輸入

5 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2

樣例輸出

1

提示

數(shù)據(jù)范圍：

30%的數(shù)據(jù)滿足：n<=100;

50%的數(shù)據(jù)滿足：n<=1000; m<=100; w<=10000;

100%的數(shù)據(jù)滿足：n<=10000; 0<=m<=5000; w<=10000;

/*
訓(xùn)練的時(shí)候總錯(cuò)在省事，
合并集合寫(xiě)成下面那份代碼的樣子，
然后處理數(shù)據(jù)的時(shí)候沒(méi)有重新查root
因?yàn)槲乙恢币詾槲液喜⒓系膶?xiě)法會(huì)把同一個(gè)集合里的元素全部直接指向root，
實(shí)際上我下面的寫(xiě)法是做不到的，只是部分直接指向了root。。。
吸取教訓(xùn)！！！
*/

#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL N = 1e4+5; struct Node {LL w;LL v; } a[N]; Node sum[N]; LL pre[N],cnt[N]; LL dp[N]; LL myFind(LL x) {return pre[x]==x?x:myFind(pre[x]); } LL myUnion(LL x,LL y) {LL fx = myFind(x);LL fy = myFind(y);if(fx != fy){if(cnt[fx] >= cnt[fy]){pre[fy] = fx;cnt[fx]+=cnt[fy];}else{pre[fx] = fy;cnt[fy] += cnt[fx];}} } int main() {LL n,m,W;scanf("%lld%lld%lld",&n,&m,&W);for(LL i = 1; i <= n; i++){scanf("%lld%lld",&a[i].w,&a[i].v);}for(LL i = 1; i <= n; i++){pre[i] = i;cnt[i] = 1;}LL x,y;for(LL i = 1; i <= m; i++){scanf("%lld%lld",&x,&y);myUnion(x,y);}for(LL i = 1; i <= n; i++){//錯(cuò)誤點(diǎn)：這里必須要再查一次root！！！！！sum[pre[i]].w += a[i].w;sum[pre[i]].v += a[i].v;}LL k = 0;for(LL i = 1; i <= n; i++){if(sum[i].v){cnt[++k] = i;}}// cout<<k<<endl;for(LL i = 1; i <= k ; i++){LL t = cnt[i];//cout<<sum[t].w<<" "<<sum[t].v<<endl;for(LL j = W; j >= sum[t].w; j--){dp[j] = max(dp[j],dp[j-sum[t].w]+sum[t].v);}}printf("%lld\n",dp[W]);return 0; }

Ac_code:

#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL N = 1e4+5; struct Node {LL w;LL v; } a[N]; Node sum[N]; LL pre[N],cnt[N]; LL dp[N]; LL myFind(LL x) {return pre[x]==x?x:myFind(pre[x]); } void myUnion(LL x,LL y) {LL fx = myFind(x);LL fy = myFind(y);if(fx != fy){pre[fx] = fy;} } int main() {LL n,m,W;scanf("%lld%lld%lld",&n,&m,&W);for(LL i = 1; i <= n; i++){scanf("%lld%lld",&a[i].w,&a[i].v);}for(LL i = 1; i <= n; i++){pre[i] = i;cnt[i] = 1;}LL x,y;for(LL i = 1; i <= m; i++){scanf("%lld%lld",&x,&y);myUnion(x,y);}for(LL i = 1; i <= n; i++){int now = myFind(pre[i]); //這里必須查一下，因?yàn)橛胁糠謕re[i]還不是它們的root的編號(hào)sum[now].w += a[i].w;sum[now].v += a[i].v;}LL k = 0;for(LL i = 1; i <= n; i++){//cout<<pre[i]<<" ";if(sum[i].v){cnt[++k] = i;}}for(LL i = 1; i <= k ; i++){LL t = cnt[i];for(LL j = W; j >= sum[t].w; j--){dp[j] = max(dp[j],dp[j-sum[t].w]+sum[t].v);}}printf("%lld\n",dp[W]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的问题 B: 小鱼的搭配购物（并查集+01背包）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。