@toc

定义

给定一个带权图，满足以下条件：

• 1.保证图中所有的点都联通
• 2.在满足条件1的情况下尽可能去掉多的边，使得所有的边权之和最小，即$\Sigma_{i=1}^{i<=m}w_i$最小。
  Read more »

@toc

Bellman-Ford 算法

Bellman-Ford算法：
$Dijkstra$类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。

@TOC

@TOC

图的基本概念

图：由顶点（vertex）和边（edge）组成。

定义

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

@TOC

题目描述

这是一个数三角的游戏。长度为1或SQRT(2)的小木棍放在一个网格上。如图所示，有水平的，垂直的或对角的。对角放置的木棍可以交叉。

关于STL的简单总结

STL

STL是Standard Template Library的简称，中文名标准模板库，惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL是C++的一部分，因此不用安装额外的库文件。

Read more »

题目描述

经过在机房里数日的切磋，LYD 从杜神牛那里学会了分离与合体，出关前，杜神牛给了他一个测试……

火柴排队

内存限制：128 MiB
时间限制：1000 ms

题目描述

涵涵有两盒火柴，每盒装有n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为： $∑(ai-bi)^2$其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。

请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

拓扑排序

拓扑排序是对一张 有向 并且 无环 的图进行遍历排序。
如果在图中所有的节点构成的序列$A$中，对于每一条边$(x, y)$：$x$都出现在$y$的前面，则序列$A$就为这张图的拓扑序。

题目描述

有一只老鼠很喜欢奶酪，但是奶酪被分别放在N个房间里，而且这些房间都有一只猫咪看守，现在它准备和猫咪们做个交易。它有M磅的猫食，想用这M磅猫食换取奶酪。在猫咪看守的每一个房间里有奶酪J[i] 磅，同时猫咪需要F[i]磅的食物，如果老鼠给猫咪F[i] (a)%的猫食，那么它就可以得到J[i] (a)%的奶酪。现在已知每只猫咪对猫食的需求量和每个房间的奶酪数，那老鼠怎样才能换得最多的奶酪呢？

定义

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
—— baidu

Read more »