题目链接 分析 此题可以暴力二分，但是只有80pts，所以不采纳这个思想。 考虑与最小生成树的关系，当所有的引力把能走的路全部封死之后，此时的\(ans\)便是最大的引力圈的半径。 step1 首先初始化\(dis[i] = m - y[i]\),把dis[k+1]设为m。 step2 然后用\(Prim\)不停遍历，如果此时找的最近节点为\(k+1\)说明已经遍历完毕，直接退出， ans更新成ans与dis[falg]之间的大者。 然后更xin\(dis[i](i∈k)\), 更新\(dis[k+1]=min(dis[k+1], y[falg])\) 最后输出\(ans/2\)。 代码 #i...

题目地址 分析 第一眼看到此题，感觉就是一道水题，直接加上前\(need\)小的白边就行了，再处理到\(n-1\)条黑边，但是，打完后突然发现有问题。。。 虽然加上了前\(need\)小的白边，但是会出现树不连通的现象，即无法构成生成树。 正解思路 二分一个增量\(mid\)(可正可负)。 跑一遍\(Kruskal\)，将所有的白边都加上\(a\)，记录构成生成树后所用到的白边，如果数量小于\(need\)就将右端点往左移，否则往右移。 最后的\(ans\)需要减去增量\(need * mid\) 代码 #include <cstdio> #include <iostream...

题目连接 分析 一道可以暴力水过去的次小生成树   step1  首先用\(Kruskal\)||\(Prim\)求出原图的一颗最小生成树，在连边的时候，用一个\(vis\)记录一下那些已经在最小生成树里面。   step2  提前暴力\(dfs\)或者\(bfs\)求出任意两点构成的环之间的最大权值 具体操作 定义函数\(dfs(int s, int u, int father, int mw1, int mw2)\) s -> 起点 u -> 终点 father 判断是否回到原起点 mw1 最大值 mw2 次大值 再用md1[s][u]保存从s -> u的最大边权值， 用...

题目链接 分析 假设有如下图两个集合 \(x\) & \(y\)。因为要构造一个完全图，所以应该将\(x\)中的\(s[x]\)个节点与\(y\)中的\(s[y]\)个节点一一连接即连接\(s[x] * s[y] - 1\)（此处减一是为了在后面单独处理原图中的\(dis[i].w\)）个节点，为了保证此完全图的最小生成树所以要用\((s[x] * s[y] - 1) * (dis[i].w + 1)\)，最后加上原图中的\(dis[i].w\)。  代码 #include <cstdio> #include <iostream> #include <al...

SCOI 滑雪与时间胶囊 题目描述 a180285 非常喜欢滑雪。 他来到一座雪山，这里分布着\(M\)条供滑行的轨道和\(N\)个轨道之间的交点（同时也是景点），而且每个景点都有一编号\(i(1<=i<=n)\)和一高度$$。a180285 能从景点\(i\)滑到景点\(j\)当且仅当存在一条\(i\)和\(j\)之间的边，且\(i\)的高度不小于\(j\)。 与其他滑雪爱好者不同， a180285 喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是 a180285 拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上...

最小生成树   定义  Kruskal算法 算法流程 具体实现  建立结构体存边 并查集维护 完整代码      定义 给定一个带权图，满足以下条件：  1.保证图中所有的点都联通 2.在满足条件1的情况下尽可能去掉多的边，使得所有的边权之和最小，即      Σ    i   =   1     i   <   =   m      w   i     \Sigma_{i=1}^{i<=m}w_i   Σi=1i<=m​wi​最小。  Kruskal算法 Kruskal是基于贪心的思想，根据以上的定义描述依次枚举     1   −   m    1-m   1−m条边，如...

图论学习笔记3    Bellman-Ford 算法    松弛 负边权操作 负权环判定   朴素实现  Spfa  思想 实现      Bellman-Ford 算法 Bellman-Ford算法：      D   i   j   k   s   t   r   a    Dijkstra   Dijkstra类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。 松弛 每次松弛操作实际上是对相邻节点的访问，第 n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径...

     最短路    多源最短路  Floyd Dijkstra  一般版本 邻接表优化 优先队列优化         多源最短路 Floyd FloydFloydFloyd是基于DPDPDP思想。 设kkk为中转点，与iii, jjj都有边相连。 那么可以得到dis[i][j]dis[i][j]dis[i][j]的最短路径的状态转移方程为： dis[k,i,j]=min(dis[k−1,i,j],dis[k−1,i,k]+dis[k−1,k,j]dis[k,i,j]=min(dis[k-1,i,j], dis[k-1,i,k]+dis[k-1,k,j]dis[k,i,j]=min(dis[...

图论学习笔记     图的基本概念 图的存储结构  邻接矩阵  邻接表   存点 加边  图的遍历  深度优先 广度优先       图的基本概念 图：由**顶点（vertex）和边（edge）**组成。 顶点—具体事物 边—具体事物之间的联系 顶点的集合     V    V   V，边的集合     E    E   E，图记为     G   =   (   V   ,   E   )    G = (V,E)   G=(V,E) 图的存储结构 一般分为两种 ： 邻接矩阵、邻接表 邻接矩阵 由一个二维数组实现,比较简单，但是在存储稠密图时比较不划算。      G   [   i   ]...

定义 树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。 —— by baidu 实现 用一个数组     b   i   t   [   i   ]    bit[i]   bit[i]表示从     [   i   −   l   o   w   b   i   t   (   x   )  ...

数三角     题目描述 输入格式 输出格式 样例  样例输入 样例输出   分析  预处理 求出连通性 判断是否构成三角形  完整代码     题目描述 这是一个数三角的游戏。长度为1或SQRT(2)的小木棍放在一个网格上。如图所示，有水平的，垂直的或对角的。对角放置的木棍可以交叉。  将木棍随意地放在网格上得到的图案可能不含三角形，也可能含一个或多个三角形。如下图所示，  (a),(b),©,(d)和(e)分别含有2,5,12,0,0个三角形。你的任务是写一个程序数出一个图案中的三角形个数。。cpp 输入格式 输入文件count.in包括N+1行： 先输入图案中木棍的个数N。下面输入这N根...

题目描述 经过在机房里数日的切磋，LYD 从杜神牛那里学会了分离与合体，出关前，杜神牛给了他一个测试…… 杜神牛造了n 个区域，他们紧邻着排成一行，编号 1 ~ n 。在每个区域里都放着一把 OI 界的金钥匙，每一把都有一定的价值，LYD 当然想得到他们了。然而杜神牛规定 LYD 不能一下子把他们全部拿走，而是每次只可以拿一把。为了尽快得到所有金钥匙，LYD 自然就用上了刚学的分离与合体特技。 一开始 LYD 可以选择 1 … n - 1 中的任何一个区域进入，我们不妨把这个区域记为k 。进入后 LYD 会在 区域发生分离，从而分离成两个小 LYD。分离完成的同时会有一面墙在 k 区域和 k ...

火柴排队  内存限制：128 MiB 时间限制：1000 ms  题目描述 涵涵有两盒火柴，每盒装有n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：      ∑   (   a   i   −   b   i    )   2     ∑(ai-bi)^2   ∑(ai−bi)2其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。 请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输...

<p> </p> <h1><a id="_0"></a>拓扑排序</h1> <p>拓扑排序是对一张 <strong>有向</strong> 并且 <strong>无环</strong> 的图进行<strong>遍历排序</strong>。<br> 如果在图中所有的节点构成的序列<span class="katex--inline"><span class...