搭配购买(buy)
时间限制: 1000 ms 内存限制: 65536 KB 提交数: 268 通过数: 117
【题目描述】Joe觉得云朵很美,决定去山上的商店买一些云朵。商店里有n朵云,云朵被编号为1,2,…...,n,并且每朵云都有一个价值。但是商店老板跟他说,一些云朵要搭配来买才好,所以买一朵云则与这朵云有搭配的云都要买。 但是Joe的钱有限,所以他希望买的价值越多越好。 【输入】第1行n,m,w,表示n朵云,m个搭配,Joe有w的钱。 第2~n+1行,每行ci,di表示i朵云的价钱和价值。 第n+2~n+1+m行,每行ui,vi,表示买ui就必须买vi,同理,如果买vi就必须买ui。 【输出】一行,表示可以获得的最大价值。 【输入样例】
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
【输出样例】
【提示】【数据范围】 30%的数据保证:n≤100 50%的数据保证:n≤1,000;m≤100;w≤1,000 100%的数据保证:n≤10,000;0≤m≤5000;w≤10,000 【算法分析】这题我们第一个任务就是把这些云朵分组集合,然后将集合看成一个整体,01背包就欧克。
【代码分析】
#include<bits/stdc++.h>
using namespace std;
#define N 10100
int fa[N],c[N],d[N],v[N],w[N];
int find(int x)
{return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{int n,m,w1;scanf("%d%d%d",&n,&m,&w1);for(int i=1;i<=n;i++){fa[i]=i;scanf("%d%d",&c[i],&d[i]);}for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);int r1=find(x),r2=find(y);if(r1!=r2){fa[r1]=r2;//一起购买的并入同一集合}}for(int i=1;i<=n;i++){int x=find(i);w[x]+=c[i];v[x]+=d[i];//同一集合的总费用算出}int tot=0;for(int i=1;i<=n;i++){if(fa[i]==i) //一个的集合根节点就只有一个,所以根节点就是一组云朵{w[++tot]=w[i];v[tot]=v[i];}}int f[N];memset(f,0,sizeof(f));for(int i=1;i<=tot;i++)//01背包for(int j=w1;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+v[i]);printf("%d",f[w1]);return 0;
}
这个代码有点不懂,待日后研究: #include<bits/stdc++.h>
using namespace std;
#define N 10100
int fa[N],c[N],d[N];
int find(int x)
{return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{int n,m,w;scanf("%d%d%d",&n,&m,&w);for(int i=1;i<=n;i++){fa[i]=i;scanf("%d%d",&c[i],&d[i]);}for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);int r1=find(x),r2=find(y);if(r1!=r2){fa[r2]=r1;//为什么不是f[r1]=r2c[r1]+=c[r2];//累加计算每个集合的总价钱d[r1]+=d[r2];}}int tot=0;for(int i=1;i<=n;i++){cout<<fa[i]<<" "<<c[i]<<" "<<d[i]<<endl;;if(fa[i]==i){c[++tot]=c[i];d[tot]=d[i];}}int f[N];memset(f,0,sizeof(f));for(int i=1;i<=tot;i++)for(int j=w;j>=c[i];j--)f[j]=max(f[j],f[j-c[i]]+d[i]);printf("%d",f[w]);return 0;
}
|