`
leili
  • 浏览: 179495 次
社区版块
存档分类
最新评论

poj 1258 prim最小生成树

阅读更多
#include <iostream>using namespace std;int a[105][105],b[105],n;int prim(int ii){   int i,j,k,min,ans=0,t;    for(i=0;i<n;i++)      b[i]=a[ii][i];    b[ii]=-1;    for(i=1;i<n;i++)    {        for(min=2<<20,j=0;j<n;j++)            if(min>b[j]&&b[j]!=-1) min=b[j],t=j;        ans+=min; b[t]=-1;        for(j=0;j<n;j++)        if(a[t][j]<b[j]) b[j]=a[t][j];    }    return ans;}int main(){   int i,j;    while(cin>>n)    {    for(i=0;i<n;i++)    for(j=0;j<n;j++)      cin>>a[i][j];    cout<<prim(0)<<endl;	    }    return 0;} 


 

分享到:
评论

相关推荐

    POJ 1751 求最小生成树prim算法(JAVA)

    标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...

    POJ1258-Agri-Net【Prim】

    普里姆算法是一种贪心算法,它从一个顶点开始,逐步扩展最小生成树,每次添加一条与当前生成树连接且权值最小的边。以下是算法的基本步骤: 1. 初始化:选择图中的任意一个顶点作为初始最小生成树的一部分。 2. 建立...

    POJ 1789 最小生成树之prim算法

    标题中的“POJ 1789 最小生成树之prim算法”指的是一个在线编程竞赛题目,来源于普林斯顿开放在线课程(POJ)平台。该题目要求参赛者实现Prim算法,这是一种解决图论问题中寻找最小生成树的经典算法。最小生成树是在...

    poj1251 最小生成树

    标题“poj1251 最小生成树”是一个编程竞赛题目,来源于著名的在线编程平台POJ(Programming Online Judge)。这个题目主要涉及图论中的一个经典算法问题——最小生成树(Minimum Spanning Tree, MST)。在图论中,...

    POJ2485-Highways【Prim】

    Prim算法可以帮助找到连接所有城市的最短路径总和,即最小生成树。 总的来说,这个压缩包提供了对POJ2485题目的完整解答,通过Prim算法解决了公路网络优化的问题,并附有详细的代码和解题思路。对于学习图论和算法...

    最小生成树(MST)问题——北京大学暑期课《ACM/ICPC竞赛训练》

    Prim算法是一种贪心算法,其基本思想是从某个顶点出发,逐步选择与当前已构建的生成树相连接的边中权重最小的边加入生成树中,直到生成树包含图中的所有顶点为止。 - **初始化**:选择一个顶点\( v \)作为起始顶点...

    最小生成树题解1

    1. POJ2485 和 POJ1258 题目都是典型的最小生成树问题,要求在给定的城市或农场之间构建网络,使得总距离最小。这两种情况都可以使用 Prim 算法或 Kruskal 算法来解决。Prim 算法从一个顶点开始,逐步添加边,每次...

    度限制最小生成树源码

    给定代码片段中使用了Prim算法来计算每个连通分量内的最小生成树,并通过扩展Prim算法(`extend_degree()`函数)来寻找每个连通分量中到根节点的最佳边,以此来构建满足度数限制的生成树。 #### 知识点三:代码分析...

    POJ1789-Truck History【Prim】

    Prim算法是一种用于求解图中最小生成树的算法。在图论中,一个连通图的最小生成树是一棵树,它包含图中的所有顶点,并且所有边的权重之和尽可能小。Prim算法是从一个顶点开始,逐步添加边,直到包含所有顶点,每次...

    次小生成树(POJ 1679 The Unique MST)

    先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...

    POJ 1639 Picnic Planning 最小度限制生成树

    1. **函数mst(int ss)**:输入参数ss代表生成树的起点,该函数通过Prim算法实现最小生成树的构建。 - 初始化距离数组`dis[]`,设置起点距离为0,其余节点距离为无穷大。 - 使用循环找到未加入生成树的最近节点,并...

    POJ2031-Building a Space Station【Prim+计算几何】

    这里运用了Prim算法,这是一种寻找图中最小生成树的经典算法,旨在以最小的总边权和连接所有顶点。计算几何则可能涉及到计算模块间的距离、方向等几何属性,以便确定最经济的连接方式。 【Prim算法】Prim算法是一种...

    POJ第1861题源码POJ第1861题源码POJ第1861题源码POJ第1861题源码

    对于POJ第1861题,参赛者可能需要读取输入数据,构建一个加权图,然后应用Prim或Kruskal算法找出最小生成树,最后输出树中边的权重总和或者某种特定格式的树结构。解题过程可能涉及到错误处理、边界条件检查以及效率...

    POJ3026-Borg Maze【BFS+Prim】

    然后,Prim算法每次从尚未加入最小生成树的节点中选择距离起点最近的一个,连接到树中,更新其他节点的距离。重复此过程,直至所有节点都被包含在内。 在提交的代码文件“POJ3026-Borg Maze【BFS+Prim】.cpp”中,...

    ACMer需要掌握的算法讲解 (2).docx

    * 最小生成树算法:prim、kruskal、POJ1789、POJ2485、POJ1258、POJ3026 * 拓扑排序:POJ1094 * 串算法:POJ1035、POJ3080、POJ1936 * 哈希表和二分查找等高效查找法:POJ3349、POJ3274、POJ2151、POJ1840、POJ2002...

    poj 2485 Highways 测试数据

    在【压缩包子文件的文件名称列表】中,"poj 2485 Highways (最小生成树)"可能是题目提供的样例输入和输出文件,用于检验自己编写的程序是否正确。这些样例通常包含了各种边界情况和特殊案例,以确保算法的鲁棒性。 ...

    POJ 1861 Network

    常见的求解最小生成树的算法有Prim算法和Kruskal算法。在这个问题中,由于需要先进行快速排序,Kruskal算法更为合适,因为它依赖于边的排序。Kruskal算法的基本步骤是: 1. 将所有边按权重从小到大排序。 2. 初始化...

    Poj中的一些题目源代码

    Prim和Kruskal是两种常见的求解最小生成树的算法。在某些情况下,图可能有唯一的最小生成树,这两个实现可能分别使用了这两种方法。 4. **P3522(slimness_kruskal变式).cpp** - "slimness"通常指的是树的直径或者...

    poj题目分类

    * 最小生成树算法:例如 Prim、Kruskal,例如 poj1789、poj2485、poj1258、poj3026。 * 拓扑排序:例如 poj1094。 * 二分图的最大匹配:例如 poj3041、poj3020。 * 最大流的增广路算法:例如 poj1459、poj3436。...

    poj解题报告2395

    常见的求解最小生成树的算法有两种:Prim算法和Kruskal算法。从代码中可以看出,这里采用的是Kruskal算法。 #### Kruskal算法详解 Kruskal算法是一种贪心算法,其核心思想是每次选取权重最小的边加入到生成树中,...

Global site tag (gtag.js) - Google Analytics