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

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
AI一键生成 PPT

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人，是不是经常需要制作各种PPT来分享我的生活和想法。但是，你们知道，有时候灵感来了，时间却不够用了！😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手！🌟 什么是Kimi？ 一款月之暗面科技有限公司开发的AI办公工具，帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师，Kimi都能够为你的办公文
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu2289（简单二分）

hdu2289（简单二分）

虽说是简单二分，但是我还是wa死了  题意：已知圆台的体积，求高度 首先要知道圆台体积怎么求：设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
pdfmake生成pdf的使用

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据，将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2