当前位置: 首页 > news >正文

沧州网站建设设计竞价服务托管公司

沧州网站建设设计,竞价服务托管公司,保定 网站制作,seo网站推广优化公司目录 1 基础知识2 模板3 工程化 1 基础知识 朴素版prim算法的关键步骤: 初始化距离数组dist,将其内的所有元素都设为正无穷大。定义集合S,表示生成树。循环n次:找到不在集合S中且距离集合S最近的结点t,用它去更新剩余…

目录

  • 1 基础知识
  • 2 模板
  • 3 工程化

1 基础知识

朴素版prim算法的关键步骤:

  1. 初始化距离数组dist,将其内的所有元素都设为正无穷大。
  2. 定义集合S,表示生成树。
  3. 循环n次:找到不在集合S中且距离集合S最近的结点t,用它去更新剩余结点到集合S的距离。
  4. 最小生成树建立完毕,边长之和等于每次的d[t]之和。

朴素版prim算法的时间复杂度为O(n^2),它用来解决稠密图的最小生成树问题。

2 模板

int n;      // n表示点数
int g[N][N];        // 邻接矩阵,存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中// 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{memset(dist, 0x3f, sizeof dist);int res = 0;for (int i = 0; i < n; i ++ ){int t = -1;for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;if (i && dist[t] == INF) return INF;if (i) res += dist[t];st[t] = true;for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);}return res;
}

3 工程化

题目1:求最小生成树。

#include <iostream>
#include <cstring>using namespace std;const int N = 510;
int g[N][N];
int d[N];
bool st[N];
int n, m;void prim() {memset(d, 0x3f, sizeof d);int res = 0;for (int i = 0; i < n; ++i) {//n次循环//找到不在集合S且距离集合S最小的结点int t = -1;for (int j = 1; j <= n; ++j) {if (!st[j] && (t == -1 || d[t] > d[j])) {t = j;}}if (i && d[t] == 0x3f3f3f3f) {cout << "impossible" << endl;return;}st[t] = true;if (i) res += d[t];//用t去更新其它结点for (int j = 1; j <= n; ++j) {if (d[j] > g[t][j]) {d[j] = g[t][j];}}}cout << res << endl;return;
}int main() {cin >> n >> m;memset(g, 0x3f, sizeof g);int a, b, c;while (m--) {cin >> a >> b >> c;g[a][b] = min(g[a][b], c);g[b][a] = min(g[b][a], c);}prim();return 0;
}
http://www.15wanjia.com/news/43218.html

相关文章:

  • 微信做色情网站重庆seo公司怎么样
  • 阳江网站建设推广公司电话百度云官方网站
  • 网站专题页策划收录
  • 手机网站安装百度优化公司
  • 做特殊单页的网站百度推广网站一年多少钱
  • 县城做网站的多么北京网络推广公司wyhseo
  • dw可以做h5网站网络营销就业前景和薪水
  • 网站开发项目计划wbs山东今日头条新闻
  • 莱芜金点子传媒电子版新塘网站seo优化
  • 外贸网站特效橙子建站怎么收费
  • 怎么看网站是用什么系统做的潍坊网站模板建站
  • 商城移动端网站开发seo首页关键词优化
  • 香港公司怎么做网站正规引流推广公司
  • 郑州网站排名外包商城网站建设
  • 济南网站建设山东酷风买卖链接网站
  • 申请网站免费谷歌搜索引擎seo
  • 哪里学做网站免费做网页的网站
  • 设计门户网站广州网站建设公司
  • 营销型网站建设原则市场调研报告怎么写范文
  • 还有哪些网站可以做淘宝活动吗搜索引擎关键词快速优化
  • ui特效网站seo关键词排名软件流量词
  • 怎么在网站里做网页seo排名怎样
  • 阿里妈妈新建网站怎么做新闻头条最新消息今天
  • 做网站比较专业的公司精准营销方式有哪些
  • 政府网站建设工作室百度广告关键词价格表
  • 营销型网站建设选择题关键词歌词完整版
  • 自己做的网站怎么上传到域名线上销售水果营销方案
  • wordpress 即时八宿县网站seo优化排名
  • 门户网站域名是什么神马seo服务
  • asp网站做搜索网页设计网站