随机搜索

发表于 | 分类于 |

eg:NOIP2003-P1041

给定传染病传染树，一个周期内只能切断一条途径，求最多能减少多少病人

贪心想法：统计切掉当前途径能减少多少病例，从多到少切

但是不同的途径在不同的时间点能减少的病人也不一样，故该贪心错误

使用随机函数寻找切掉的节点，通过设置权值使程序偏向寻找可能性最大的节点（辅以最优性剪枝），重复该操作直至无点可切

多次重复上述操作取最优值，最优解大概率正确

srds，这题是错题，数据极水。。直接用dfs遍历所有情况就可以