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

网站建设欣赏推广运营是做什么的

网站建设欣赏,推广运营是做什么的,wordpress医疗模板,自己域名做网站题目: 寻宝 题目描述 在世界的某个区域,有一些分散的神秘岛屿,每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路,方便运输。 不同岛屿之间,路途距离不同,国王希望你可以规划建公路的方案&#xf…

题目: 寻宝

题目描述

在世界的某个区域,有一些分散的神秘岛屿,每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路,方便运输。

不同岛屿之间,路途距离不同,国王希望你可以规划建公路的方案,如何可以以最短的总公路距离将 所有岛屿联通起来(注意:这是一个无向图)。

给定一张地图,其中包括了所有的岛屿,以及它们之间的距离。以最小化公路建设长度,确保可以链接到所有岛屿;

提取关键: 存在一些点, 存在一些边, 每条边都有一定的代价, 求将所有点连通的最小代价;

Kruskal 算法

思路

将边按代价从小到大进行排序, 然后从代价最小的开始遍历, 尽量选择代价小的边加入结果集中, 最终使得整个图连通;

当我们遍历到一条边, 这条边所连的两个顶点本身就已经连通时, 那么这条边是多余的, 如果加入, 会产生环;

并查集

并查集的作用与代码在上一篇文章中有详细介绍, 可以到专栏中查看;

前文介绍了并查集的两大作用: 判断两点之间是否连通以及求集合大小; 这里, 介绍另一个用途: 判断无向图中是否存在环;

在无向图中, 如果一条边的两个端点本来就是连通的(处在同一集合中), 那么这个边的加入必然会使得图中产生 “环”
假设图中有 1, 2, 3 三个顶点, 有 [1, 2], [1, 3] 两条边, 现在考虑加入 [2, 3] 这条边, 原本结点 2 和 结点 3 就已经处于连通状态, 现在加入 [2, 3] 必定导致图中出现环状结构;

利用并查集, 就可以在将边纳入[边集]之前进行判断, 判断当前边的加入是否会导致出现环;

1  ____  2\      /\    /3

代码

import java.util.*;public class Main{public static void main(String[] args){kruskal();}// 求最小生成树代价; 对边代价排序, 由小到大连接即可, 连接过程中用 Union 判断环private static void kruskal(){Scanner sc = new Scanner(System.in);int vNum = sc.nextInt();int eNum = sc.nextInt();int[][] edges = new int[eNum][3];for(int i = 0; i < eNum; i++){for(int j = 0; j < 3; j++){edges[i][j] = sc.nextInt();}}Arrays.sort(edges, (e1, e2) -> Integer.compare(e1[2], e2[2]));Union union = new Union(vNum);int res = 0;for(int[] edge : edges){if(!union.isSame(edge[0], edge[1])){res += edge[2];union.join(edge[0], edge[1]);}}System.out.println(res);}
}class Union{private int[] father;public Union(int size){father = new int[size + 1];for(int i = 1; i <= size; i++){father[i] = i;}}public int root(int i){int temp = i;while(father[temp] != temp){temp = father[temp];}father[i] = temp;return temp;}public boolean isSame(int i1, int i2){return root(i1) == root(i2);}public void join(int i1, int i2){father[root(i2)] = root(i1);}
}

上一篇 【最小生成树】(一) 预备知识 并查集

http://www.rdtb.cn/news/1331.html

相关文章:

  • 有哪些建设网站公司吗sem推广是什么意思呢
  • 中国人民建设人行网站首页提高工作效率整改措施
  • 建立个人网站的目的百度app广告
  • 企业网站 价格0元免费做代理
  • 广州商城型网站360推广联盟
  • 东莞网络推广运营团队百度seo关键词优化排行
  • 一个人做公司管理网站网络营销推广价格
  • 怎么装wordpress优化网站搜索排名
  • 网站开发和c语言网站推广排名服务
  • 网店推广有哪些方法百度推广优化排名怎么收费
  • 鹤壁做网站推广企业网站推广策划
  • 做评测系统网站首先要干嘛seo文章是什么
  • 网站空间哪里的好搜索引擎优化的目的是
  • 27寸显示器网站建设微信公众号软文怎么写
  • 自己做网站视频教程黑帽seo是什么意思
  • 网站制作在哪里找网络营销方案策划案例
  • 做二手货车网站关键词优化怎么弄
  • 深圳罗湖网站制作公司最新营销模式
  • 商丘做网站哪家好公司网站如何seo
  • 做羞羞的事情的网站苏州网站制作
  • 纯div css网站哪些广告平台留号码
  • 做网站用什么格式的图片建网站怎么建
  • 设计本官方网站电脑版重庆森林经典台词梁朝伟
  • 大淘客官网做的网站打不开如何网络营销
  • 做伤残鉴约号网站投放广告的网站
  • 网站开发研究背景西安seo代理计费
  • 传统网站建设架构seo优化排名是什么
  • wordpress 修改css关键词优化seo公司
  • 网站中英文转换怎么做seo营销推广多少钱
  • 做视频网站用什么开发网络营销五种方法