最小生成树 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使用Javassist动态生成HelloWorld类

Java使用Javassist动态生成HelloWorld类

《Java使用Javassist动态生成HelloWorld类》Javassist是一个非常强大的字节码操作和定义库,它允许开发者在运行时创建新的类或者修改现有的类,本文将简单介绍如何使用Javass... 目录1. Javassist简介2. 环境准备3. 动态生成HelloWorld类3.1 创建CtC
阅读更多...
Python 基于http.server模块实现简单http服务的代码举例

Python 基于http.server模块实现简单http服务的代码举例

《Python基于http.server模块实现简单http服务的代码举例》Pythonhttp.server模块通过继承BaseHTTPRequestHandler处理HTTP请求,使用Threa... 目录测试环境代码实现相关介绍模块简介类及相关函数简介参考链接测试环境win11专业版python
阅读更多...
Python从Word文档中提取图片并生成PPT的操作代码

Python从Word文档中提取图片并生成PPT的操作代码

《Python从Word文档中提取图片并生成PPT的操作代码》在日常办公场景中,我们经常需要从Word文档中提取图片,并将这些图片整理到PowerPoint幻灯片中,手动完成这一任务既耗时又容易出错,... 目录引言背景与需求解决方案概述代码解析代码核心逻辑说明总结引言在日常办公场景中，我们经常需要从 W
阅读更多...
C#使用Spire.XLS快速生成多表格Excel文件

C#使用Spire.XLS快速生成多表格Excel文件

《C#使用Spire.XLS快速生成多表格Excel文件》在日常开发中,我们经常需要将业务数据导出为结构清晰的Excel文件,本文将手把手教你使用Spire.XLS这个强大的.NET组件,只需几行C#... 目录一、Spire.XLS核心优势清单1.1 性能碾压：从3秒到0.5秒的质变1.2 批量操作的优雅
阅读更多...
Python使用python-pptx自动化操作和生成PPT

Python使用python-pptx自动化操作和生成PPT

《Python使用python-pptx自动化操作和生成PPT》这篇文章主要为大家详细介绍了如何使用python-pptx库实现PPT自动化,并提供实用的代码示例和应用场景,感兴趣的小伙伴可以跟随小编... 目录使用python-pptx操作PPT文档安装python-pptx基础概念创建新的PPT文档查看
阅读更多...
python连接sqlite3简单用法完整例子

python连接sqlite3简单用法完整例子

《python连接sqlite3简单用法完整例子》SQLite3是一个内置的Python模块,可以通过Python的标准库轻松地使用,无需进行额外安装和配置,：本文主要介绍python连接sqli... 目录1. 连接到数据库2. 创建游标对象3. 创建表4. 插入数据5. 查询数据6. 更新数据7. 删除
阅读更多...
Jenkins的安装与简单配置过程

Jenkins的安装与简单配置过程

《Jenkins的安装与简单配置过程》本文简述Jenkins在CentOS7.3上安装流程,包括Java环境配置、RPM包安装、修改JENKINS_HOME路径及权限、启动服务、插件安装与系统管理设置... 目录www.chinasem.cnJenkins安装访问并配置JenkinsJenkins配置邮件通知
阅读更多...
在ASP.NET项目中如何使用C#生成二维码

在ASP.NET项目中如何使用C#生成二维码

《在ASP.NET项目中如何使用C#生成二维码》二维码（QRCode）已广泛应用于网址分享,支付链接等场景,本文将以ASP.NET为示例,演示如何实现输入文本/URL,生成二维码,在线显示与下载的完整... 目录创建前端页面（Index.cshtml）后端二维码生成逻辑（Index.cshtml.cs）总结
阅读更多...
Python实现数据可视化图表生成(适合新手入门)

Python实现数据可视化图表生成(适合新手入门)

《Python实现数据可视化图表生成(适合新手入门)》在数据科学和数据分析的新时代,高效、直观的数据可视化工具显得尤为重要,下面：本文主要介绍Python实现数据可视化图表生成的相关资料,文中通过... 目录前言为什么需要数据可视化准备工作基本图表绘制折线图柱状图散点图使用Seaborn创建高级图表箱线图热
阅读更多...
SQLServer中生成雪花ID(Snowflake ID)的实现方法

SQLServer中生成雪花ID(Snowflake ID)的实现方法

《SQLServer中生成雪花ID(SnowflakeID)的实现方法》：本文主要介绍在SQLServer中生成雪花ID(SnowflakeID)的实现方法,文中通过示例代码介绍的非常详细,... 目录前言认识雪花ID雪花ID的核心特点雪花ID的结构（64位）雪花ID的优势雪花ID的局限性雪花ID的应用场景
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2