luogu P1455 搭配购买

题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有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：

输出样例#1：

说明

30%的数据满足：n<=100

50%的数据满足：n<=1000;m<=100;w<=1000;

100%的数据满足：n<=10000;0<=m<=5000;w<=10000.

思路

先用并查集，把要搭配在一起的价钱和价值全部累加放在flag的价钱和价值那儿

然后01背包裸题。。。

Codes

 1 program buy;
 2 uses math;
 3 const
 4   inf='buy.in';
 5   outf='buy.out';
 6 var
 7   i,x,y,n,m,h,j:longint;
 8   father,w,c:array[1..10000] of longint;
 9   f:array[0..10000] of longint;
10 
11 
12 function find(apple:Longint):longint;
13 begin
14     if father[apple]<>0 then father[apple]:=find(father[apple])
15       else exit(apple);
16     find:=father[apple];
17 end;
18 
19 procedure union(a,b:longint);
20 var
21   t1,t2:longint;
22 begin
23     t1:=find(a);
24     t2:=find(b);
25     if t1<>t2 then
26      begin
27          father[t2]:=t1;
28          w[t1]:=w[t1]+w[t2];
29          c[t1]:=c[t1]+c[t2];
30      end;
31 end;
32 
33 begin
34   //assign(input,inf);
35   //assign(output,outf);
36   //reset(input); rewrite(output);
37 
38   readln(n,m,h);
39   for i:= 1 to n do
40     readln(w[i],c[i]);
41   for i:= 1 to m do
42     begin
43         read(x,y);
44         union(x,y);
45     end;
46 
47   for i:= 1 to n do
48     if father[i]=0 then
49     for j:= h downto w[i] do
50        f[j]:=max(f[j],f[j-w[i]]+c[i]);
51   writeln(f[h]);
52 
53   close(input);
54   close(output);
55 end.