最小生成树 Prime算法 简单题

2024-06-15 19:48
文章标签 算法 简单 最小 生成 prime

本文主要是介绍最小生成树 Prime算法 简单题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

相比于Kruskal算法，Prime算法是以顶点为主导地位的

将图中所有的点分到两个集合  S和T中去  S中的点表示图中已经已经选择了的点  T中的点表示待选择的点

每次从T中选择到S中的点的距离最小的点加入到S中去

 

prime（）算法中会有三个数组

low[]  存放顶点集合T内各顶点到集合S中 各顶点权值最小的边的权值

nearvex[]  记录集合T内各顶点到集合S中哪个顶点最近   当nearvex[i]为-1时  表示顶点i在集合S中

edge[i][j]表示i到j的权值

 

ZOJ 1586

题意很容易理解  没啥说的 

这个题不需要输出选择的边 所有low[]数组可以与nearvex[]数组的功能合并

代码如下：

<span style="font-family:KaiTi_GB2312;font-size:18px;"><span style="font-family:KaiTi_GB2312;font-size:18px;">
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD  10009
#define MAXN  100100
#define INF 0x7fffffff
#define FOR(i,a,b)  for(int i=a;i<=b;i++)
#define FOV(i,a,b)  for(int i=a;i>=b;i--)
#define REP(i,a,b)  for(int i=a;i<b;i++)
#define REV(i,a,b)  for(int i=a-1;i>=b;i--)
#define MEM(a,x)    memset(a,x,sizeof a)
#define ll __int64using namespace std;
int n;
int low[1010];
int edge[1010][1010];
int ad[1010];void prime()
{int sum=0;low[0]=-1;for(int i=1;i<n;i++)low[i]=edge[0][i];for(int i=1;i<n;i++){int mi=INF;int k;for(int j=0;j<n;j++){if(low[j]!=-1&&low[j]<mi){k=j;mi=low[j];}}sum+=mi;low[k]=-1;for(int j=0;j<n;j++){if(edge[k][j]<low[j])low[j]=edge[k][j];}}printf("%d\n",sum);
}int main()
{
//freopen("ceshi.txt","r",stdin);int tc;scanf("%d",&tc);while(tc--){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&ad[i]);for(int i=0;i<n;i++)for(int j=0;j<n;j++){int x;scanf("%d",&x);if(i==j)    edge[i][j]=INF;else{edge[i][j]=x+ad[i]+ad[j];}}MEM(low,0);prime();}return 0;
}
</span></span>


 

ZOJ 1258  POJ 1789

题意没啥好说的   将两个字符串比较  给edge赋值  就可以了 

<span style="font-family:KaiTi_GB2312;font-size:18px;">#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD  10009
#define MAXN  100100
#define INF 0x7fffffff#define FOR(i,a,b)  for(int i=a;i<=b;i++)
#define FOV(i,a,b)  for(int i=a;i>=b;i--)
#define REP(i,a,b)  for(int i=a;i<b;i++)
#define REV(i,a,b)  for(int i=a-1;i>=b;i--)
#define MEM(a,x)    memset(a,x,sizeof a)
#define ll __int64using namespace std;char ch[2010][8];
int low[2010];
int edge[2010][2010];
int n;void prime()
{int sum=0;low[0]=-1;for(int i=1;i<n;i++)low[i]=edge[0][i];for(int i=1;i<n;i++){int mi=INF;int j;for(int k=0;k<n;k++){if(low[k]!=-1&&low[k]<mi){j=k;mi=low[k];}}sum+=mi;low[j]=-1;for(int k=0;k<n;k++){if(edge[j][k]<low[k])low[k]=edge[j][k];}}printf("The highest possible quality is 1/%d.\n",sum);
}int main()
{
//freopen("ceshi.txt","r",stdin);while(scanf("%d\n",&n)!=EOF){if(n==0)  break;for(int i=0;i<n;i++)scanf("%s",ch[i]);for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j)  edge[i][j]=INF;if(i<j){int num=0;for(int k=0;k<7;k++){if(ch[i][k]!=ch[j][k])  num++;}edge[i][j]=edge[j][i]=num;}}}prime();}return 0;
}
</span>


 

 zoj 1914   poj 2349

在前哨之间建立网络，要保证任意两个前哨之间能通过网络进行联系

前哨直接也可以通过卫星频道进行联系  有S个卫星频道   就是有S个前哨可以有卫星频道  可以组成S-1条边

所以  求到最小生成树时   有P个点 有P-1条边  len数组中存储的是0-- P-2（由小到大）  要去除边长最长的前

S-1条边  所以 就是P-2-（S-1）=P-S-1   输出sqrt(len[p-s-1])就可以了

<span style="font-family:KaiTi_GB2312;font-size:18px;">#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD  10009
#define MAXN  100100
#define INF 0x7fffffff#define FOR(i,a,b)  for(int i=a;i<=b;i++)
#define FOV(i,a,b)  for(int i=a;i>=b;i--)
#define REP(i,a,b)  for(int i=a;i<b;i++)
#define REV(i,a,b)  for(int i=a-1;i>=b;i--)
#define MEM(a,x)    memset(a,x,sizeof a)
#define ll __int64using namespace std;
int s,p;
int x[510],y[510];
int low[510];
int edge[510][510];
int len[510];
int cnt;void prime()
{for(int i=0;i<p;i++)low[i]=edge[0][i];low[0]=-1;cnt=0;for(int i=1;i<p;i++){int mi=INF,j;for(int k=0;k<p;k++){if(low[k]!=-1&&low[k]<mi){j=k;mi=low[k];}}len[cnt++]=mi;low[j]=-1;for(int k=0;k<p;k++){if(edge[j][k]<low[k])low[k]=edge[j][k];}}
}int main()
{
//freopen("ceshi.txt","r",stdin);int tc;scanf("%d",&tc);while(tc--){scanf("%d%d",&s,&p);for(int i=0;i<p;i++){scanf("%d%d",&x[i],&y[i]);}for(int i=0;i<p;i++)for(int j=0;j<p;j++){if(i==j)edge[i][j]=INF;else{edge[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);edge[j][i]=edge[i][j];}}prime();sort(len,len+cnt);
//    cout<<cnt<<endl;
//    for(int i=0;i<cnt;i++)
//        cout<<len[i]<<"  ";
//    cout<<endl;
//    cout<<len[p-s-1]<<endl;printf("%.2lf\n",sqrt((double)(len[p-s-1]*1.0)));}return 0;
}
</span>

 POJ 1258

<span style="font-family:KaiTi_GB2312;font-size:18px;">#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD  10009
#define MAXN  100100
#define INF 0x7fffffff#define FOR(i,a,b)  for(int i=a;i<=b;i++)
#define FOV(i,a,b)  for(int i=a;i>=b;i--)
#define REP(i,a,b)  for(int i=a;i<b;i++)
#define REV(i,a,b)  for(int i=a-1;i>=b;i--)
#define MEM(a,x)    memset(a,x,sizeof a)
#define ll __int64using namespace std;int low[110],nearvex[110];
int edge[110][110];
int res;
int n;void prime()
{low[0]=-1;for(int i=1;i<n;i++){low[i]=edge[0][i];}for(int i=1;i<n;i++){int mi=INF;int j;for(int k=0;k<n;k++){if(low[k]!=-1&&low[k]<mi){j=k;mi=low[k];}}res+=mi;low[j]=-1;for(int k=0;k<n;k++){if(edge[j][k]<low[k])low[k]=edge[j][k];}}printf("%d\n",res);
}int main()
{
//freopen("ceshi.txt","r",stdin);while(scanf("%d",&n)!=EOF){for(int i=0;i<n;i++)for(int j=0;j<n;j++){scanf("%d",&edge[i][j]);if(i==j)edge[i][j]= INF;}res=0;prime();}return 0;
}
</span>

 poj 3026

题意反正我没怎么看懂 看别人的题解才知道大概是个什么意思

要先通过bfs求出两个点之间的最短距离（A S）

然后再用prime求最小生成树

这个题比较坑  读入两个整数之后还有好多的空格  也要把这些空格读掉

题中给的数据范围感觉有问题  数组一开始开小了  总是过不了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>#define eps 1e-8
#define op operator
#define MOD  10009
#define MAXN  100100
#define INF 0x7fffffff#define FOR(i,a,b)  for(int i=a;i<=b;i++)
#define FOV(i,a,b)  for(int i=a;i>=b;i--)
#define REP(i,a,b)  for(int i=a;i<b;i++)
#define REV(i,a,b)  for(int i=a-1;i>=b;i--)
#define MEM(a,x)    memset(a,x,sizeof a)
#define ll __int64using namespace std;
int x,y;
char mp[200][200];
int vis[200][200];
int edge[200][200];
int low[200];
int node[200][200];
int res,num;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};struct point
{int n,m;int step;bool operator<(const point p)const{return step>p.step;}
};point p,q;
priority_queue<point> Q;void bfs(int n,int m)
{int nn=node[n][m];MEM(vis,0);vis[n][m]=1;p.n=n; p.m=m; p.step=0;Q.push(p);while(!Q.empty()){q=Q.top();  Q.pop();if(node[q.n][q.m]){
//        cout<<node[q.n][q.m]<<"  ";int mm=node[q.n][q.m];edge[nn][mm]=q.step;
//        cout<<edge[nn][mm]<<endl;}for(int i=0;i<4;i++){p.n=q.n+dir[i][0];  p.m=q.m+dir[i][1];if(p.n>=0&&p.n<y&&p.m>=0&&p.m<x&&!vis[p.n][p.m]&&mp[p.n][p.m]!='#'){vis[p.n][p.m]=1;p.step=q.step+1;Q.push(p);}}}
}void prime()
{low[1]=-1;for(int i=2;i<=num;i++)low[i]=edge[1][i];for(int i=2;i<=num;i++){int mi=INF;int j;for(int k=1;k<=num;k++){if(low[k]!=-1&&low[k]<mi){j=k;mi=low[k];}}res+=mi;low[j]=-1;for(int k=1;k<=num;k++){if(edge[j][k]<low[k])low[k]=edge[j][k];}}printf("%d\n",res);
}char tmp[60];int main()
{
//freopen("ceshi.txt","r",stdin);int tc;scanf("%d",&tc);while(tc--){scanf("%d %d",&x,&y);gets(tmp);num=0;MEM(node,0);for(int i=0;i<y;i++){gets(mp[i]);for(int j=0;j<x;j++){if(mp[i][j]=='A'||mp[i][j]=='S'){num++;node[i][j]=num;}}}
//        for(int i=0;i<y;i++)
//        {
//            for(int j=0;j<x;j++)
//            {
//                cout<<mp[i][j];
//            }
//            cout<<endl;
//        }for(int i=0;i<y;i++)for(int j=0;j<x;j++)if(node[i][j])bfs(i,j);
//        for(int i=1;i<=num;i++)
//        {
//            for(int j=1;j<=num;j++)
//            {cout<<edge[i][j]<<" ";
//                if(i==j)
//                    edge[i][j]=INF;
//            }cout<<endl;
//        }res=0;prime();}return 0;
}

 

这篇关于最小生成树 Prime算法 简单题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1064414。

相关文章

Java使用Spire.Barcode for Java实现条形码生成与识别

Java使用Spire.Barcode for Java实现条形码生成与识别

《Java使用Spire.BarcodeforJava实现条形码生成与识别》在现代商业和技术领域,条形码无处不在,本教程将引导您深入了解如何在您的Java项目中利用Spire.Barcodefor... 目录1. Spire.Barcode for Java 简介与环境配置2. 使用 Spire.Barco
阅读更多...
GO语言实现串口简单通讯

GO语言实现串口简单通讯

《GO语言实现串口简单通讯》本文分享了使用Go语言进行串口通讯的实践过程,详细介绍了串口配置、数据发送与接收的代码实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 目录背景串口通讯代码代码块分解解析完整代码运行结果背景最近再学习 go 语言，在某宝用5块钱买了个
阅读更多...
SpringBoot整合Apache Spark实现一个简单的数据分析功能

SpringBoot整合Apache Spark实现一个简单的数据分析功能

《SpringBoot整合ApacheSpark实现一个简单的数据分析功能》ApacheSpark是一个开源的大数据处理框架,它提供了丰富的功能和API,用于分布式数据处理、数据分析和机器学习等任务... 目录第一步、添加android依赖第二步、编写配置类第三步、编写控制类启动项目并测试总结ApacheS
阅读更多...
SpringBoot集成iText快速生成PDF教程

SpringBoot集成iText快速生成PDF教程

《SpringBoot集成iText快速生成PDF教程》本文介绍了如何在SpringBoot项目中集成iText9.4.0生成PDF文档,包括新特性的介绍、环境准备、Service层实现、Contro... 目录SpringBoot集成iText 9.4.0生成PDF一、iText 9新特性与架构变革二、环
阅读更多...
idea-java序列化serialversionUID自动生成方式

idea-java序列化serialversionUID自动生成方式

《idea-java序列化serialversionUID自动生成方式》Java的Serializable接口用于实现对象的序列化和反序列化,通过将对象转换为字节流来存储或传输,实现Serializa... 目录简介实现序列化serialVersionUID配置使用总结简介Java.io.Seripyth
阅读更多...
Java中的随机数生成案例从范围字符串到动态区间应用

Java中的随机数生成案例从范围字符串到动态区间应用

《Java中的随机数生成案例从范围字符串到动态区间应用》本文介绍了在Java中生成随机数的多种方法,并通过两个案例解析如何根据业务需求生成特定范围的随机数,本文通过两个实际案例详细介绍如何在java中... 目录Java中的随机数生成：从范围字符串到动态区间应用引言目录1. Java中的随机数生成基础基本随
阅读更多...
C++简单日志系统实现代码示例

C++简单日志系统实现代码示例

《C++简单日志系统实现代码示例》日志系统是成熟软件中的一个重要组成部分,其记录软件的使用和运行行为,方便事后进行故障分析、数据统计等,：本文主要介绍C++简单日志系统实现的相关资料,文中通过代码... 目录前言Util.hppLevel.hppLogMsg.hppFormat.hppSink.hppBuf
阅读更多...
C#自动化生成PowerPoint(PPT)演示文稿

C#自动化生成PowerPoint(PPT)演示文稿

《C#自动化生成PowerPoint(PPT)演示文稿》在当今快节奏的商业环境中,演示文稿是信息传递和沟通的关键工具,下面我们就深入探讨如何利用C#和Spire.Presentationfor.NET... 目录环境准备与Spire.Presentation安装核心操作：添加与编辑幻灯片元素添加幻灯片文本操
阅读更多...
Python实现Word文档自动化的操作大全(批量生成、模板填充与内容修改)

Python实现Word文档自动化的操作大全(批量生成、模板填充与内容修改)

《Python实现Word文档自动化的操作大全(批量生成、模板填充与内容修改)》在职场中,Word文档是公认的好伙伴,但你有没有被它折磨过？批量生成合同、制作报告以及发放证书/通知等等,这些重复、低效... 目录重复性文档制作，手动填充模板，效率低下还易错1.python-docx入门：Word文档的“瑞士
阅读更多...
使用python生成固定格式序号的方法详解

使用python生成固定格式序号的方法详解

《使用python生成固定格式序号的方法详解》这篇文章主要为大家详细介绍了如何使用python生成固定格式序号,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... 目录生成结果验证完整生成代码扩展说明1. 保存到文本文件2. 转换为jsON格式3. 处理特殊序号格式（如带圈数字）4
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2