首页 > 代码库 > 洛谷——P1455 搭配购买
洛谷——P1455 搭配购买
https://www.luogu.org/problem/show?pid=1455
题目描述
明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有n朵云，云朵已经被老板编号为1，2，3，……,n,并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。
输入输出格式
输入格式：
第1行n,m,w,表示n朵云，m个搭配和你现有的钱的数目
第2行至n+1行，每行ci,di表示i朵云的价钱和价值
第n+2至n+1+m ，每行ui,vi表示买ui就必须买vi,同理，如果买vi就必须买ui
输出格式：
一行，表示可以获得的最大价值
输入输出样例
输入样例#1：
5 3 103 103 103 105 10010 11 33 24 2
输出样例#1：
1
说明
30%的数据满足：n<=100
50%的数据满足：n<=1000;m<=100;w<=1000;
100%的数据满足：n<=10000;0<=m<=5000;w<=10000.
初衷是练Tarjan的，结果~~~
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 const int N(1e5+15); 7 int n,m,money; 8 int u,v,f[N],fa[N]; 9 struct Type10 {11 int val,use;12 } thing[N];13 14 int find(int x)15 {16 return fa[x]==x?x:fa[x]=find(fa[x]);17 }18 19 void combine(int x,int y)20 {21 int fx=find(x), fy=find(y);22 if(fx!=fy)23 {24 fa[fy]=fx;25 thing[fx].use+=thing[fy].use;26 thing[fx].val+=thing[fy].val;27 thing[fy].use=0; thing[fy].val=0;28 }29 }30 31 int main()32 {33 scanf("%d%d%d",&n,&m,&money);34 for(int i=1;i<=n;i++) fa[i]=i;35 for(int i=1;i<=n;i++)36 scanf("%d%d",&thing[i].use,&thing[i].val);37 for(;m;m--)38 {39 scanf("%d%d",&u,&v);40 combine(u,v);41 }42 for(int i=1;i<=n;i++)43 if(thing[i].use||thing[i].val)44 for(int j=money;j>=thing[i].use;j--)45 f[j]=max(f[j],f[j-thing[i].use]+thing[i].val);46 printf("%d",f[money]);47 return 0;48 }
洛谷——P1455 搭配购买
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。