题意:有N个物品,承重上限为M,有K组物品互斥关系,互斥关系有传递性,即1与2互斥,2与3互斥,1与3也互斥
给出每个物品的花费和价值,求承重上限内的最大价值总和
n<=1000,m<=1000,k<=1000
c[i]<=1000 w[i]<=10
思路:日常刷水
因为互斥关系有传递性,并查集后就是分组背包DP
1 var dp:array[0..1000]of longint; 2 a,c,w,f:array[1..1000]of longint; 3 n,m,i,j,k,ans,x,y,p,q:longint; 4 5 function max(x,y:longint):longint; 6 begin 7 if x>y then exit(x); 8 exit(y); 9 end; 10 11 function find(k:longint):longint; 12 begin 13 if f[k]<>k then f[k]:=find(f[k]); 14 find:=f[k]; 15 end; 16 17 begin 18 assign(input,'Vijos1250.in'); reset(input); 19 assign(output,'Vijos1250.out'); rewrite(output); 20 21 readln(n,m,k); 22 23 for i:=1 to n do read(c[i],w[i]); 24 for i:=1 to n do f[i]:=i; 25 for i:=1 to k do 26 begin 27 readln(x,y); 28 p:=find(x); q:=find(y); 29 if p<>y then f[q]:=p; 30 end; 31 for i:=1 to n do 32 begin 33 q:=0; 34 for j:=1 to n do 35 if find(j)=i then begin inc(q); a[q]:=j; end; 36 for j:=m downto 0 do 37 for k:=1 to q do 38 if j-w[a[k]]>=0 then dp[j]:=max(dp[j],dp[j-w[a[k]]]+c[a[k]]); 39 end; 40 ans:=0; 41 for i:=0 to m do ans:=max(ans,dp[i]); 42 writeln(ans); 43 44 close(input); 45 close(output); 46 end.