《信息学奥赛一本通》1387：搭配购买(buy)

1387：搭配购买(buy)

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 2596 通过数: 1290

【题目描述】
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。

解析：
并查集+01背包，将所有有搭配的云朵合并成一个物品再DP求解即可。

#include
#define N 10001
using namespace std;int n,m,w,ui,vi,dad[N],ans=0;
int cloud[N][2],item[N][2],f[N];int Find(int x)				//并查集操作模板
{if(dad[x]==x)return x;return dad[x]=Find(dad[x]);
}void Union(int fa,int so)
{fa=Find(fa);so=Find(so);if(fa!=so){dad[so]=fa;cloud[fa][0]+=cloud[so][0];		//合并云朵的价值和价钱cloud[fa][1]+=cloud[so][1];}
}void solve()				//01背包
{int itemnum=0;for(int i=1;i<=n;i++)if(dad[i]==i)			//转化物品{item[++itemnum][0]=cloud[i][0];item[itemnum][1]=cloud[i][1];}memset(f,0,sizeof(f));for(int i=1;i<=itemnum;i++)for(int v=w;v>=item[i][0];v--)f[v]=max(f[v],f[v-item[i][0]]+item[i][1]);
}int main() 
{scanf("%d %d %d",&n,&m,&w);for(int i=1;i<=n;i++){scanf("%d %d",&cloud[i][0],&cloud[i][1]);dad[i]=i;}for(int i=1;i<=m;i++){scanf("%d %d",&ui,&vi);Union(ui,vi);}solve();printf("%d",f[w]);
}

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