题意:求一个图所有生成树中 最大边与最小边的差的最小值。
解题思路:要求max-min的最小值 就是要让max最小 min 最大。 而我们的kruskal算法求得的当前生成树的max一定是最小的。所以我们只要将min从小到大遍历,然后求得最小值即可。(语言表达的有点绕口,建议参照代码结合着看)。
#include "iostream" #include "algorithm" using namespace std; #define MAXSIZE 6000 #define INF 100000 struct node{ int u; int v; int w; }; node edge[MAXSIZE]; int f[MAXSIZE]; int e; int n,m; void addnode(int u,int v,int w) { edge[e].u=u; edge[e].v=v; edge[e].w=w; e++; } bool cmp(node &a,node &b) { return a.w<b.w; } int findeset(int x) { if(x==f[x]) return x; else return f[x]=findeset(f[x]); } int kruskal(int s) { int i; for (i=1;i<=n;i++) { f[i]=i; } int fnum=n;//集合个数 for (i=s;i<e;i++) { if (findeset(edge[i].u)!=findeset(edge[i].v))//不属于同一集合 { //union f[findeset(edge[i].v)]=findeset(edge[i].u); fnum--; if (fnum==1)//合并完成 { return edge[i].w-edge[s].w; } } } return INF;//无法得到一颗生成树 } int main() { //freopen("in.txt","r",stdin); while(true) { e=0; scanf("%d%d",&n,&m); if ((n==0)&&(m==0)) { break; } int a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c); addnode(a,b,c); } //求所有生成树中 最大边与最小边差的最小值 max-min 最小 要max 最小 min 最大 //而kruskal 方法中求得的生成树 max一定是最小 所以我们只要min从小到大取值即可 // sort(edge,edge+e,cmp); int ans=INF; for (int i=0;i<e;i++) { int t =kruskal(i); if (t<ans) { ans=t; } } if (ans!=INF) { printf("%d\n",ans); } else { printf("-1\n"); } } return 0; }
相关推荐
标题“poj1251 最小生成树”是一个编程竞赛题目,来源于著名的在线编程平台POJ(Programming Online Judge)。这个题目主要涉及图论中的一个经典算法问题——最小生成树(Minimum Spanning Tree, MST)。在图论中,...
在图论领域,克鲁斯卡尔(Kruskal)算法是一种用于解决最小生成树问题的有效方法。这个问题涉及到在一个加权无向图中找到一棵包括所有顶点的树,其边的权重之和尽可能小。POJ 1679 是一个编程竞赛题目,旨在通过实践...
4. POJ3522 题目稍显复杂,要求找到一棵生成树,使得最大边权与最小边权的差最小。这需要一种特殊的最小生成树策略,可能需要对边进行特定的排序和选择,以最小化权值差异。 对于这些题目,理解最小生成树的基本...
构造最小生成树主要有两种经典算法:Prim算法和Kruskal算法。 **Prim算法** Prim算法是一种贪心算法,其基本思想是从某个顶点出发,逐步选择与当前已构建的生成树相连接的边中权重最小的边加入生成树中,直到生成...
3. **P1679(Unique_MST_prim).cpp 和 P1679(Unique_MST_kruskal).cpp** - 这两个文件都涉及了“唯一最小生成树”问题。Prim和Kruskal是两种常见的求解最小生成树的算法。在某些情况下,图可能有唯一的最小生成树...
对于POJ第1861题,参赛者可能需要读取输入数据,构建一个加权图,然后应用Prim或Kruskal算法找出最小生成树,最后输出树中边的权重总和或者某种特定格式的树结构。解题过程可能涉及到错误处理、边界条件检查以及效率...
在【压缩包子文件的文件名称列表】中,"poj 2485 Highways (最小生成树)"可能是题目提供的样例输入和输出文件,用于检验自己编写的程序是否正确。这些样例通常包含了各种边界情况和特殊案例,以确保算法的鲁棒性。 ...
* 最小生成树算法:最小生成树算法是指计算图的最小生成树的算法,如 prim、kruskal。 * 拓扑排序:拓扑排序是指计算图的拓扑排序的算法,如 poj1094。 * 二分图的最大匹配:二分图的最大匹配是指计算二分图的最大...
* 最小生成树算法:例如 Prim、Kruskal,例如 poj1789、poj2485、poj1258、poj3026。 * 拓扑排序:例如 poj1094。 * 二分图的最大匹配:例如 poj3041、poj3020。 * 最大流的增广路算法:例如 poj1459、poj3436。...
- 最小生成树算法:如Prim算法和Kruskal算法,用于找出图中的最小生成树,如`poj1789, poj2485`。 - 拓扑排序:适用于有向无环图,用于确定任务的执行顺序,如`poj1094`。 - 二分图的最大匹配:如匈牙利算法,...
【标题】"POJ 1861 Network"是一个经典的计算机科学问题,它涉及到图论中的网络连接,并要求我们利用并查集(Disjoint Set)数据结构来检测图中的环路,同时应用快速排序算法来求解最小生成树。这个问题在ACM(国际...
* 最小生成树算法:prim、kruskal、POJ1789、POJ2485、POJ1258、POJ3026 * 拓扑排序:POJ1094 * 串算法:POJ1035、POJ3080、POJ1936 * 哈希表和二分查找等高效查找法:POJ3349、POJ3274、POJ2151、POJ1840、POJ2002...
- **解释**:最小生成树算法主要包括Prim算法和Kruskal算法。 ##### (4) 拓扑排序 - **例题**:poj1094 - **解释**:拓扑排序是对有向无环图的一种排序方式,可以用来解决依赖关系的问题。 ##### (5) 匹配算法 - *...
总结来说,这个压缩包提供了一个使用最小生成树算法解决POJ2485题目的实例,它涉及了图论、贪心算法、C++编程和在线编程竞赛实践等多个IT领域的知识点。通过分析和学习这个解题代码,我们可以加深对最小生成树算法的...
- (poj1789, poj2485, poj1258, poj3026):介绍普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal),用于寻找加权无向图的最小生成树。 4. **拓扑排序**: - (poj1094):适用于有向无环图(DAG)的一种排序方式,...
Kruskal算法是一种贪心算法,其核心思想是每次选取权重最小的边加入到生成树中,直到生成树包含所有顶点为止。具体步骤如下: 1. **初始化**:将图中的所有顶点看作独立的集合。 2. **排序**:按照边的权重从小到大...
#### 最小生成树 Prim算法和Kruskal算法分别基于贪心策略和并查集数据结构,用于在带权图中找到连接所有顶点的最小总权重的树结构。 #### 拓扑排序 适用于有向无环图,帮助分析任务依赖关系,如poj1094所示。 ####...
**算法基础**:报告可能会首先介绍一些基本的算法知识,如排序(快速排序、归并排序、堆排序等)、搜索(深度优先搜索、广度优先搜索)、图论(最短路径算法Dijkstra、Floyd-Warshall、Prim或Kruskal最小生成树算法...
图论算法涉及图的数据结构和基于图的各种操作,如最短路径算法(Dijkstra、Bellman-Ford、Floyd)、最小生成树算法(Prim、Kruskal)。Dijkstra算法用于寻找图中两点间的最短路径,而Bellman-Ford算法可以处理带有负...
4. **最小生成树**:如果涉及网络的基础设施,可能需要找到最小生成树(例如Kruskal's Algorithm或Prim's Algorithm),以最小化破坏成本。 5. **最短路径算法**:Dijkstra's Algorithm或Floyd-Warshall Algorithm...