热门标签
更多>
搜索结果
查询Tags标签: 判正环,共有 2条记录-
算法提高课-图论-负环-AcWing 1165. 单词环:spfa判正环、二分、01分数规划
文章目录 题目分析题目链接题目分析来源:acwing 分析: 如何建图? 这样建图。以样例举例。起点是前两个字母,终点是末尾两个字母,边权是字符串的长度。 我们求的是什么呢? 题目要求Σ边权Σ1(点的个数)\frac{\Sigma{边权}}{\Sigma{1}(点的个数)}Σ1(点的个数)Σ边权…
2021/4/7 20:09:53 人评论 次浏览 -
算法提高课-图论-负环-AcWing 361. 观光奶牛:spfa判正环、负环、01分数规划、二分
文章目录 题目分析题目链接题目分析来源:acwing 分析: 题目要求ΣfiΣgi\frac{\Sigma{f_i}}{\Sigma{g_i}}ΣgiΣfi的最大值,这种问题称为01分数规划,通俗点说,就是一堆的和除以一堆的和,要求比值最大。 对于本题 我们可以通过二分来做,二分啥呢?就是对于一个…
2021/4/7 14:08:31 人评论 次浏览