搜索加最优化剪枝居然过了？

看来数据比较烂啊……

不过再想想，毕竟只是树，用邻接表确实应该不慢啊……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

虽说是0MS过了,但是心中有点不塌实.搞那个自相似的时候,感觉有更快的方法得一棵变更后的树,但是我是把除去根的那个要切断的节点之外的所有儿子节点放到一个TREE[0]里,再按价值(深度*子树节点个数)排序,每次只搜价值排前10的儿子节点.第一次交把300看成200..

构造自相似，经典

终于懂了

貌似有向树处理时只要按编号大小来确定是儿子还是父亲就好了.

数据不强的缘故吧,如果要加个递归的maketree()有点烦

void dfs(int tnow)//疾病已经传播到tnow周期

{

if(effected>=minnum) return;

bool found;

int i,j;

found=false;//是否有子结点

for(i=1;i

毫不简单

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

搜索真是好方法

一个看起来是SB的剪枝提速10倍！！！

A*真的很好用....

program p1101;

var k1,k2,hao,mm,r,min,x,y,wh,i,j,k,m,n:longint;

a:array[0..301,0..301]of longint;

p:array[0..301]of longint;

code,f,w1,w2:array[0..301]of longint;

s1,s2,s:array[0..301]of longint;

ok:array[0..301]of boolean;

procedure total(v:longint);

var i,j,k:longint;

begin

s1[v]:=0;

s2[v]:=a[v][0];

for I:=1 to a[v][0] do

total(a[v][i]);

for i:=1 to a[v][0] do

s1[v]:=s1[v]+s1[a[v][i]];

s1[v]:=s1[v]+1;

end;

procedure work(v:longint);

var i:longint;

begin

ok[v]:=false;

for i:=1 to a[v][0] do

work(a[v][i]);

end;

begin

readln(n,mm);

fillchar(a,sizeof(a),0);

fillchar(p,sizeof(p),0);

p[1]:=-1;

for i:=1 to mm do

begin

readln(x,y);

IF p[y]0 then

begin

wh:=x;

x:=y;

y:=wh;

end;

p[y]:=x;

inc(a[x][0]);

a[x][a[x][0]]:=y;

end;

total(1);

for i:=1 to n do dec(s1[i]);

i:=1;

j:=1;

f[1]:=1;

code[1]:=0;

while im then m:=code[i];

for i:=1 to n do w2[code[i]]:=i;

for i:=n downto 1 do w1[code[i]]:=i;

for k1:=0 to 100 do

begin

k2:=100-k1;

fillchar(ok,sizeof(ok),1);

for i:=1 to n do s[i]:=s1[i]*k1+s2[i]*k2;

for i:=1 to m do

begin

wh:=0;

hao:=0;

for j:=w1[i] to w2[i] do

if ok[f[j]] then

if s[f[j]]>=wh then

begin

wh:=s[f[j]];

hao:=j;

end;

work(F[hao]);

end;

r:=0;

for i:=1 to n do if not ok[i] then inc(r);

IF R>MIN THEN

MIN:=R;

end;

write(N-min);

end.

疯了

随便贪=ac

我随便加了个多次贪心就全部0ms

疯了

随便搜=ac

我随便加了个最优性剪枝就全部0ms

时间恶心了...

如果你是贪搜，记得把停止上限改到20

否则第九组会WA

编译通过...

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

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

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

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

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

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

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

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

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

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

好慢~

编译通过...

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

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

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

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

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

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

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

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

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

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

为什么搜索这么快，。。。。。。不解-_-|

貌似数据没有错,第九个点我的破搜索搜出来就是55

贪心是错误的,楼下已经有牛给出了反例

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

难度不是很大。。

就是有向图处理那里有点难！

注意搜索的时候考虑好就可以了！！

一开始以为是节点I给感染，，谁知道是节点1 是一！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

就是猛搜的，没别的啊

http://wysoviet.blog.hexun.com/22573521_d.html

编译通过...

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

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

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

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

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

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

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

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

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

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

这个题啊……

伤心…………

用暴力搜索+最优化剪枝。

就是说，先把读入数据初始化，以1为根节点建一棵想象中的树，其实不用建出来，只要知道谁的儿子有多少、是谁就行了，之后深搜，忽略……

vijos怎么可以禁用数学库!!!

编译不过￥%&￥%*#￥……#

白瞎了我的程序可以顺秒所有数据…………

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

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

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

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

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

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

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

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

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

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