HBUACM

在带权有向图G中，求G中的任意一对顶点间的最短路径问题，也是十分常见的一种问题。 解决这个问题的一个方法是执行n次迪杰斯特拉算法，这样就可以求出每一对顶点间的最短路径，执行的时间复杂度为O(n3)。而另一种算法是由弗洛伊德提出的，时间复杂度同样是O(n3)，但算法的形式简单很多。 在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并使用Floyd算法求出每一对顶点间的最短路径长度。 输入格式:输入的第一行包含1个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。 输出格式:共有n行，每行有n个整数，表示源点至每一个顶点的最短路径长度。 如果不存在从源点至相应顶点的路径，输出-1。对于某个顶点到其本身的最短路径长度，输出0。 请在每个整数后输出一个空格，并请注意行尾输出换行。 输入样例:1234540 3 0 10 0 4 02 0 0 00 0 1 ...

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。 输入格式:输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。 输出格式:输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。 输入样例:123456789101112131415166 151 2 51 3 31 4 71 5 41 6 22 3 42 4 62 5 22 6 63 4 63 5 13 6 14 5 104 6 85 6 3 输出样例:112 思路：​ 该题为最小生成树问题，一般有两种算法，Prim算法、Kruskal算法。这里边的个数M≤3N，说明边的数量级与结点个数一致，使用Kruskal算法更好。如下采用Kruskal算法 代码：12345678910111213141516171819202122232425262728293031323334 ...

本题目要求通过读入无向网的边的信息（省略了各顶点的信息，仅用顶点编号来表示），构造图，并利用Dijkstra算法，求出指定源点到其它各点的最短路径。 输入样例:第一行，两个整数，顶点数vN和边数eN。以后若干行，是相关边的信息，无向图的边是对称的，只输入一半的边（小编号到大编号的，间以空格），最后两行各一个整数，前一个指定源点，后一个指定的查询的终到点。（注意，示例中34条边，只输入了17条边的信息） 123456789101112131415161718192010 340 1 20 3 51 2 51 3 22 4 82 5 43 5 43 6 24 7 54 5 25 6 35 7 95 8 76 8 77 8 37 9 48 9 808 输出样例:在一行中输出从源点到指定终点的短路径及代价，注意：所有符号均为西文符号。 10-->1-->3-->6-->8:13 思路：​ 最短路径的模板题 ，Dijkstra算法是解决单源最短路径问题的贪心算法 ​ 大体思路为先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，知道求出从源点 ...

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。 输入格式：输入在第一行给出一个正整数N（≤104），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人： K P[1] P[2] ⋯ P[K] 其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104。 之后一行给出一个非负整数Q（≤104），是查询次数。随后Q行，每行给出一对被查询的人的编号。 输出格式：首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。 输入样例：1234567843 10 1 22 3 44 1 5 7 83 9 6 4210 53 7 输出样例：12310 2YN 思路：​ 并查集的变形题目，通过根节点是否相同判断是否为同一个部落 代码：12345678910111213141 ...

给出一个并查集，请完成合并和查询操作。 输入格式:第一行包含两个整数N、M，表示共有N个元素和M个操作。 接下来M行，每行包含三个整数Z*i、Xi、Yi*。 当Z**i=1时，将X*i与Y*i所在的集合合并。 当Z**i=2时，输出X*i与Y*i是否在同一集合内，是的话输出Y；否则的话输出N。 输出格式:对于每一个Z**i=2的操作，对应一行输出，每行包含一个大写字母，为Y或者N。 输入样例:123456784 72 1 21 1 22 1 21 3 42 1 41 2 32 1 4 输出样例:1234NYNY 数据规模:对于30%的数据，N<=10，M<=20； 对于70%的数据，N<=100，M<=1000； 对于100%的数据，N<=10000，M<=200000。 思路：​ 该题为模板题目，主要有两步 ​ 1）合并 merge ​ 2）查找 find ​ 注意：该题需要路径压缩 代码：1234567891011121314151617181920212223242526272829303132333435363 ...

“侧影”就是从左侧或者右侧去观察物体所看到的内容。例如上图中男生的侧影是从他右侧看过去的样子，叫“右视图”；女生的侧影是从她左侧看过去的样子，叫“左视图”。 520 这个日子还在打比赛的你，也就抱着一棵二叉树左看看右看看了…… 我们将二叉树的“侧影”定义为从一侧能看到的所有结点从上到下形成的序列。例如下图这棵二叉树，其右视图就是 { 1, 2, 3, 4, 5 }，左视图就是 { 1, 6, 7, 8, 5 }。 于是让我们首先通过一棵二叉树的中序遍历序列和后序遍历序列构建出一棵树，然后你要输出这棵树的左视图和右视图。 输入格式：输入第一行给出一个正整数 N (≤20)，为树中的结点个数。随后在两行中先后给出树的中序遍历和后序遍历序列。树中所有键值都不相同，其数值大小无关紧要，都不超过 int 的范围。 输出格式：第一行输出右视图，第二行输出左视图，格式如样例所示。 输入样例：12386 8 7 4 5 1 3 28 5 4 7 6 3 2 1 输出样例：12R: 1 2 3 4 5L: 1 6 7 8 5 思路：​ 根据树的中序和后序遍历序列建立树，得到树的层次遍历序列 ...

全球浏览器的市场虽已基本成型，但除了头部的 Chrome 一骑绝尘之外，后面的几大浏览器角逐战仍在继续，不过，有时候其中的竞争方式让人摸不清头脑。 近日据外媒 ghacks.net 报道，当在 Firefox 浏览器中打开苹果的商务网站网址（https://business.apple.com/）时，页面会显示一条“您的浏览器不支持”的提示信息。 然而，此时的 Firefox 已更新到了最新版本，但是Firefox Stable、Firefox ESR 和 Firefox Nightly 等不同版本都会出现上述提示。 这也让不少用户和开发者感到纳闷，这到底是 Firefox 浏览器自身开发原因导致的网站不兼容，还是苹果的故意为之？ 背后的两层因素针对这一问题，苹果公司给出的解决方案是，建议使用 Safari 浏览器，以及微软的 Edge 和 Google 的 Chrome，它们都可以访问商务网站，以及大多数基于 Chromium 的浏览器也会正常显示。当采用 Brave、Opera 浏览器时，也能正常访问。 关键就是一到Firefox 这里，就会出现上文的提示。苹果并未就为什么不支持 ...

C语言标准：对象、类型、常量、字面量本文中的某些关于C语言的内容与C++并不完全一致，请注意区分。 对象（Object）对象指数据存储的区域。并不是只有C++中的 class 才被称为对象，例如： 123int a; // a 是一个对象int* b; // b 是一个对象int c[6]; // c 是一个对象 C语言中其实没有变量的说法，通常说的变量准确地来说其实是对象，当然在不是很严肃的场合成为变量也无伤大雅，这里较真一下。 类型（Type）类型决定了如何解释对象或表达式结果的值的含义。 这里先列出C语言的基本类型（方便起见，省略了几乎没人用的_Complex和_Imaginary）： void char 标准有符号整数类型（Standard signed integer type）：signed char，short int，int，long int，long long int（C99） 标准无符号整数类型（Standard unsigned integer type）：_Bool（C99），unsigned char，unsigned short int，unsign ...

Github 知识分享简介：GitHub是用于版本控制和协作的代码托管平台。它可以让您和其他人在任何地方协同工作。 主要功能介绍： 创建和使用存储库: New repository 创建启动并管理新分支: 权威主分支:master,对分支进行修改,可以提取更新到主分支. 切换到其他分支：git checkout 分支名 对文件进行更改并将其作为提交, 打开pull请求(合作核心):通过拉取需求方式推送到GitHub,在创建拉取请求前对比查看更改差异,确认修改之后便可创建拉取请求; 合并拉取请求:打开并合并拉取请求,审核讨论; 仓库配置及初始化命令 Git config –global user.name/email ‘your name/your email’ Git remote add origin ***.git 连接远程仓库 更改，git add file_changed 提交 git commit -m ‘some note’ Git 的基本流程如下： 创建或修改文件 使用 git add 命令添加新创建或修改的文件（未追踪）到本地的缓存区（Index ...

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。对于深度为 D 的，有 N 个结点的二叉树，若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点，这样的树就是完全二叉树。 给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。 输入格式：输入在第一行中给出正整数 N（≤30），即树中结点个数。第二行给出后序遍历序列，为 N 个不超过 100 的正整数。同一行中所有数字都以空格分隔。 输出格式：在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔，行首尾不得有多余空格。 输入样例：12891 71 2 34 10 15 55 18 输出样例：118 34 55 71 2 10 15 91 思路：​ 因为是完全二叉树，完全可以采用数组存储。 ​ 题目给的是后序遍历，那么可以采用后序遍历进行建树，然后层序遍历对于数组来说就很简单了，直接从前到后输出就可以了 代码：12345678910111213141516171819#include <bits/stdc++.h>using namespace std;int n, ...