Description

“Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)”

Dijkstra算法

主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

主要思想是每次找到离”已成图“最近的一个顶点，然后将该顶点连入图，然后更新“已成图”到其他顶点的最短路径。贪心算法。

该算法要求图中不存在负权边！！！(无负权边自然无负权环)

马航MH370失联

2014年3月8日凌晨，马航MH370号班机从吉隆坡国际机场起飞，机上共载有239人，其中有154名中国人（中国大陆153人，中国台湾1人）。

该班机原定计划于北京时间早晨6：30抵达北京首都国际机场，但起飞后不足一小时便在马来西亚与越南海域的交界处，土珠岛以南约140海里及哥打巴鲁东北东约90海里处与马国梳邦空管中心（空中交通管制中心）失去联系。

最小生成树

最小生成树是一副连通加权无向图中一棵权值最小的生成树

主要可以使用Prim和Kruskal算法(借助并查集)实现

稠密图、点少边多：Prim

稀疏图、边多点少：Kruskal

关于并查集

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

特点是看似并不复杂，但数据量极大 。

是一种树型的数据结构，用于处理一些不相交集合(Disjoint Sets)的合并及查询问题 。

求解组合数 C（n，m）

暂时有三种方法：

1.存在数组里递归求解

2.较为生猛地求解（连乘连除）

3.改良版（乘一次除一次）

Description

给定一个有向图，若图无环，则将其进行拓扑排序并输出，否则输出IMPOSABLE。

Input

第一行为两个整数n(1<=n<=1000)、m(1<=m<=100000)； 之后m行，每行两个整数a、b(0 < a, b <= n)表示一条从a到b的有向边。

Description

In the future ,One day, tom feel so happy ,because he have a date with a girl,but they don’t live in the same city , so tom want you help him find the fastest way to the girl’s city,You should note that with the development of technology, transport can go beyond the speed of light, so the time you spend would be less than zero, but if you return to the past you can not have the date with the girl,there n(1<n<=100) city in this country and three are m(1<m<1000) roads in this country;

筛法求素数

用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。

spfa算法（优化）

spfa算法通常用于求含负权边的单源最短路径，以及判负权环。

允许输入有重边（Dijkstra不可）