编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

DFS + BFS

第九组我放弃了 全部DFS要超时 加上贪心策略就是56 不知道答案的55怎么来的 放弃了 做点降RP的事情 CHEAT

DFS。

先要预处理一下，弄清谁是儿子谁是“老子”

搜索时一个剪枝就够了：if 当前感染的人数>已经求出的答案then 回溯。

还有，我开始用邻接矩阵，超时2个点，改邻接表……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Geedy对于极端数据会出错：

其中一棵子树是退化成一条链，即使当前节点最多，但是

它传染的非常慢，一次只能传一个人，当然是砍完其他的再来砍它

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

搜索果然是好东西...

啊……做件不知道能不能算是攒人品的事：这道题第九个测试点，vijos上给出的答案是错误的……标准答案应该是56

下面贴一下我的思路：用贪心找上界剪枝，然后再搜索。

通过情况如下（比较……令牛无视）：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

其實這一題用連表二元組更容易實現.

我不晓得gyz113的贪心是怎么cheat过的。

但是..他真的很胀..

其实又是lj一个

数据里节点间的关系不是按正常顺序给的，一定要注意处理。这个地方我栽了n次……

做件加RP的事 数据中会出现2 1这样的数据,WA的人要注意了.

因为j,k两个人是互通的,建树的时候要注意处理这样的数据,不然就是直接输出1...

貌似一个弱弱的分支定界+改变搜索顺序就差不多了.

据说当时这个数据硬搜过的点不多,现在的Puppy实在高效。

贪心是错误的。

DFS建树，DP求人数，bfs+随机化=AC(according to ZRN神牛)

并查贪心会错。。。

最多60。。。搜索。。。

没有递归的程序不知道能不能过。。。。

写得有点像并查集。。。。自己调试都不过。。。修改中。。。

现在调试过了。。。 交上去10+的wating，，，，十分无语。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

直接深搜，只是不知道为什么时间这么恶心。。。。

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

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

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

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

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

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

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

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

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

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

这题无语了。。。。硬搜的

请问有没有什么好点的剪枝？

居然硬搜就可以...