总算A了!!!

太辛苦了。

N多细节问题！！！！！

并查集+背包

一次秒杀!

并查集+分组背包=一次AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

最后打成READ了呜呜

话说分组背包很强大

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一次AC！好题！并查集预处理+分组背包

背包9讲理 循环顺序确实有些不太对

我想我已经疯了 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

提交N次的30分。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

天真的以为肯定是DP悲剧了。。。。。。。。。。。。。。。。。。。。。。。。。。

最终在一个过程中发现了那个万恶的错误。。。。。。。。。。。。。。。。。。。。

修改前...

for i:=1 to n do

if father[i]=i then

begin

inc(all);

b[i]:=all;

vc[all]:=1;

fv[all,1]:=v[i];

fw[all,1]:=w[i];

end

else

begin

p:=b[father[i]];

inc(vc[p]);

fv[p,vc[p]]:=v[i];

fw[p,vc[p]]:=w[i];

end;

修改后...

begin

for i:=1 to n do

if father[i]=i then

begin

inc(all);

b[i]:=all;

vc[all]:=1;

fv[all,1]:=v[i];

fw[all,1]:=w[i];

end;

for i:=1 to n do

if father[i]i then

begin

p:=b[father[i]];

inc(vc[p]);

fv[p,vc[p]]:=v[i];

fw[p,vc[p]]:=w[i];

end;

end;

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

囧一个。。。滚动数组的f1打成了f就没过了。。

说正事吧，这题其实不复杂，就是并查集加分组背包，不过感觉背包九讲里的一维数组伪代码貌似有点问题，我是用滚动数组来解决空间问题的

PS:此题能一维数组解么？我没说是用滚动数组的方法，知道的还请站内信告诉下，谢谢了。。。

背包九讲造福百姓啊~

不过里面讲的分组背包的伪代码是

for 所有的组k

for 所有的i属于组k

for v=V..0

f[v]=max{f[v],f[v-c[i]]+w[i]}

不对吧！！！！！！！！因为同组优先的话，可能造成冲突的。

应该是

for 所有的组k

for v=V..0

for 所有的i属于组k

f[v]=max{f[v],f[v-c[i]]+w[i]}

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

传说中的分组背包

其实就和金明的预算方案反一下吗，分组背包只取一个

要细心.....

40分的，我找到原因了

除了在getFather()函数里和初始化

不要直接访问father[]数组

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

太垃圾了我

`\秒杀`\

其实也不怎么难

我是通过DFS将整一条之链揪出来(据说叫floodfill^-^)

然后就是一个 分组背包问题 (背包9讲中有讲到,背包9讲是好东西,一定要看)

其中 我还用了滚动数组,因为N

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

五分钟学完并查集和分组背包 WA了一次 还可以

汗啊，半小时写完的代码结果改了一下午.........

并查集写错了

我郁闷了....很久..很久...

---|---|---|---|---|---|---|---|---|---|---|-

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

---|---|---|---|---|---|---|---|---|---|--

并查集+前向星+分组背包=AC

谁能给个数据啊，我总是4个点，哭！！

Orz DD_engi

一套背包九讲不知帮助了多少迷茫中的人..

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

其实不用并查集的。。。大家都怎么了? 典型的floodfill + dp

花半小时学并查集...

花10分钟学分组背包...

花半小时编程...

我快吐了...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

并查集

function findf(x:integer):integer;

begin

if f[x]=x then exit(x) ;

f[x]:=findf(f[x]);

exit(f[x]);

end;

for i:= 1 to m do

begin

f[i]:=i;

ng[i]:=0 ;

readln(p[i],w[i]);

end;

for i:= 1 to n do

begin

readln(x,y);

fx:=findf(x);

fy:=findf(y);

f[fx]:=fy;

end;

for i:= 1 to m do

begin

fi:=findf(i);

inc(ng[fi]);

g[fi,ng[fi]]:=i;

end;

分组背包

for i:= 1 to m do

if ng[i] > 0 then

for j:= bw downto 0 do

for k:= 1 to ng[i] do

begin

a:=g;

if j - w[a] >= 0 then

if bb[j] < bb[j-w[a]] + p[a] then

bb[j]:=bb[j-w[a]] + p[a];

end;