首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    「2017 Multi-University Training Contest 8」2017多校训练8

    求有向图最大生成树,要求n的父节点尽量小。 我们将所有wi变为-wi,这题就变成了有向图最小生成树的模板题。对于f(n)尽可能小的要求,可以令所有wi扩大1000倍,然后 对于yi=n的点将1000-xi计入wi中,这样就保证了在W尽可能大的情况下f(n)尽可能小。有向图最小生成树的部分我们可以 O(nm)解决,大体思路是先找到每个点边权最小的父向边,然后这样连边可能会构成一些环,我们把这些环缩成一个点,然后把这个环向外连的边的权值减去向内连的边的权值,然后将这个图缩小,重复上述操作直至不再构成环。由于每次点数至少会减1,所以这样的操作至多做O(n)次,因此时间复杂度就是O(n*m)。 朱刘算法中不能记录路径,其中的fa[i]对应缩点后的下标。不过没关系,父节点非常好求,就是答案对1000取模。

    01

    算法与数据结构(五) 普利姆与克鲁斯卡尔的最小生成树(Swift版)

    上篇博客我们聊了图的物理存储结构邻接矩阵和邻接链表,然后在此基础上给出了图的深度优先搜索和广度优先搜索。本篇博客就在上一篇博客的基础上进行延伸,也是关于图的。今天博客中主要介绍两种算法,都是关于最小生成树的,一种是Prim算法,另一个是Kruskal算法。这两种算法是很经典的,也是图中比较重要的算法了。 今天博客会先聊一聊Prim算法是如何生成最小生成树的,然后给出具体步骤的示例图,最后给出具体的代码实现,并进行测试。当然Kruskal算法也是会给出具体的示例图,然后给出具体的代码和测试用例。当然本篇博客中

    07
    领券