最小生成树 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。

相关文章

Python实现自动化Word文档样式复制与内容生成

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现：样式与表格的深度复制1. 表格复制（含样式与内容）2
阅读更多...
python如何生成指定文件大小

python如何生成指定文件大小

《python如何生成指定文件大小》：本文主要介绍python如何生成指定文件大小的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python生成指定文件大小方法一(速度最快)方法二(中等速度)方法三(生成可读文本文件–较慢)方法四(使用内存映射高效生成
阅读更多...
C/C++ chrono简单使用场景示例详解

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》：本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示
阅读更多...
Maven项目中集成数据库文档生成工具的操作步骤

Maven项目中集成数据库文档生成工具的操作步骤

《Maven项目中集成数据库文档生成工具的操作步骤》在Maven项目中,可以通过集成数据库文档生成工具来自动生成数据库文档,本文为大家整理了使用screw-maven-plugin（推荐）的完... 目录1. 添加插件配置到 pom.XML2. 配置数据库信息3. 执行生成命令4. 高级配置选项5. 注意事
阅读更多...
MybatisX快速生成增删改查的方法示例

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2
阅读更多...
windows和Linux安装Jmeter与简单使用方式

windows和Linux安装Jmeter与简单使用方式

《windows和Linux安装Jmeter与简单使用方式》：本文主要介绍windows和Linux安装Jmeter与简单使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录Windows和linux安装Jmeter与简单使用一、下载安装包二、JDK安装1.windows设
阅读更多...
使用雪花算法产生id导致前端精度缺失问题解决方案

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面：本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.
阅读更多...
使用Python自动化生成PPT并结合LLM生成内容的代码解析

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤：代码片段：2. 应用 JSON 样式到
阅读更多...
SpringBoot实现二维码生成的详细步骤与完整代码

SpringBoot实现二维码生成的详细步骤与完整代码

《SpringBoot实现二维码生成的详细步骤与完整代码》如今,二维码的应用场景非常广泛,从支付到信息分享,二维码都扮演着重要角色,SpringBoot是一个非常流行的Java基于Spring框架的微... 目录一、环境搭建二、创建 Spring Boot 项目三、引入二维码生成依赖四、编写二维码生成代码五
阅读更多...
Android与iOS设备MAC地址生成原理及Java实现详解

Android与iOS设备MAC地址生成原理及Java实现详解

《Android与iOS设备MAC地址生成原理及Java实现详解》在无线网络通信中,MAC（MediaAccessControl）地址是设备的唯一网络标识符,本文主要介绍了Android与iOS设备M... 目录引言1. MAC地址基础1.1 MAC地址的组成1.2 MAC地址的分类2. android与I
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2