信奥一本通1387：搭配购买(buy)

【题目描述】

Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有nn朵云，云朵被编号为1，2，…，n1，2，…，n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

【输入】

第1行n，m，wn，m，w，表示nn朵云，mm个搭配，Joe有ww的钱。

第2~n+1行，每行cici，didi表示ii朵云的价钱和价值。

第n+2~n+1+m行，每行uiui，vivi，表示买uiui就必须买vivi，同理，如果买vivi就必须买uiui。

【输出】

一行，表示可以获得的最大价值。

【输入样例】

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

【输出样例】

1

【提示】

【数据范围】

30%的数据保证：n≤100n≤100；

50%的数据保证：n≤1,000；m≤100；w≤1,000n≤1,000；m≤100；w≤1,000；

100%的数据保证：n≤10,000；0≤m≤5000；w≤10,000n≤10,000；0≤m≤5000；w≤10,000。

【思路】首先是利用并查集把各组归类，但是归类完要记得还需要利用0/1背包，因为不一定只买一组，选定那些组合，再最终得出答案。

#include
using namespace std;
//并查集之后还要装背包！！因为不一定只能买一组 
const int maxn=10005;
int fa[maxn],rk[maxn]={},w[maxn];
void make(){iota(fa,fa+maxn,0);}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
bool same(int a,int b){a=find(a);b=find(b);return a==b;}
void unite(int a,int b){if(same(a,b))return;a=find(a);b=find(b);if(rk[a] nd;
int dp[maxn];//也是maxp 
int main()
{ios_base::sync_with_stdio(false),cin.tie(nullptr);make();int n,m,p;cin>>n>>m>>p;for(int i=1;i<=n;i++){cin>>rk[i]>>w[i];}for(int i=0;i>a>>b;unite(a,b);}for(int i=1;i<=n;i++){if(fa[i]==i&&rk[i]<=p){nd.push_back(i);}}for(auto i:nd){for(int j=p;j>=0;j--){if(j>=rk[i])dp[j]=max(dp[j],dp[j-rk[i]]+w[i]);else break;}}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！