灌溉农田

    技术2022-07-11  107

    Part1 【usaco2013 mar】灌溉农田(irrigation)解题

    这道题在考试的时候用了一个0分暴力,最后也是听了最小生成树的方法做出来的。

    题目描述 由于最近缺少降雨,农夫约翰决定在他的N块农田之间建立一个供水管网。每块的位置可以用一个二维坐标来表示(xi,yi),在第i块地和第j块地之间修建一个管道的话,代价是(xi - xj)^2 + (yi - yj)^2。农夫约翰想要建立一个花费代价最小的供水管网,使得他所有的地都能被连接在一起(使得水能够通过一系列的管道流到各个田地里去)。不幸的是,建造管道的人拒绝建造花费代价小于C的单条管道。请帮助约翰计算最少需要花费多少代价,才能建成这个供水管网。

    输入 第一行是两个正整数N和C。 第2行到第N+1行,每行两个整数,表示xi和yi。

    输出 输出建立供水管网的最小代价,如果不能建立供水管网,就输出-1。

    样例输入 3 11 0 2 5 0 4 3

    样例输出 46 解题思路:首先我们知道了,这道题是让我们生成一个最小的水管网络,就是一个最小生成的树。这样就变成了一道模板题,只不过要屏蔽一下费用<C的路径。 所以在这里我们重点叙述一下最小生成树的方法。

    Part2 最小生成树

    最小生成树普遍的两种方法就是prim和kruskal。 Prim法这是一种类似于贪心的方法,也被称为“加点法”。n次循环,每次加一个点,每次找最短的边去连线。当n-1次循环结束时,这棵最小的树就形成了。 例题参考:最优布线问题(wire.cpp) 推荐题解 Kruskal法这是一种利用并查集来生成的方法。

    Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序(一般使用快排),并认为每一个点都是孤立的,分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合,那么就把这条边加入最小生成树,这两个不同的集合就合并成了一个集合;如果这条边连接的两个点属于同一集合,就跳过。直到选取了n-1条边为止。(引用一本通的一段话)

    注:第一种方法适合稠密图,而第二种适合稀疏图。 好的回到这道题目,我们可以用Prim法去解。首先我们要把每一条边设为一个非常大的数(在后面要区别开来),然后按照输入的方法将这个数组赋值,除去<C的边。最后,用Pirm去跑一遍就是n^2的时间复杂度,不会爆。最后也是完成了这道题。 以下给出Prim的部分

    for (int i=1;i<n;++i){ min=900000000; for (int j=1;j<=n;++j) if (b[j]==0&&a[j]<min){ min=a[j]; t=j; } b[t]=1; ans+=a[t]; for (int j=1;j<=n;++j) if (b[j]==0&&f[j][t]<a[j]) a[j]=f[j][t]; } for (int i=1;i<=n;++i) if (b[i]!=1){ printf("-1"); return 0; } printf("%d",ans);

    好了,这道题就这样完成了。谢谢大家的观看,留个赞吧!

    Processed: 0.011, SQL: 9