算法学习之路|有向无环图（DAG）求最长路

原题为2017暑假acm亚洲区预赛乌鲁木齐赛区的H题，看紫书时看到DAG就把这题找了出来，毕竟也是少数自己参加过的比赛。

本题题意：在有n个站点，m条从高到低的滑雪路径的滑雪场上，找出一条加起来滑的最远的路径（只能从高到低划）。转化一下就是，给一张有向无环图（无负权边），求最长路。

因为是水题，没有卡空间或时间，也不需要考虑数据溢出，还算良心=_=

ac代码：（敲了好久啊——真是菜）

写这道题顺便回顾了一下邻接表，不过用数组表示的邻接表看起来可能没有指针表示或者用stl来的直观。

好久不敲代码，初始化都没注意，卡了好久才发现。

顺便记一下邻接表：

u，v，w三个数组分别保存边的起始点，指向点和边的权值。

first数组存储每一点的其中一条从此点出发的边的编号，例如：first[2]=5表示编号为2的点的其中一条边的编号为5.

next数组存储以某一点为出发点的一条边的下一条边的编号，例如：next[5]=3表示编号为5的边的出发点（比如说点1）的下一条边的编号是3。这样就可以通过forst和next数组遍历每一个点的每一条边了，且对于稀疏图而言，占内存远小于邻接矩阵。

许多简单的dp问题可以转化为DAG问题。紫书上的例子：选择不同面值的硬币到达指定面额，可以转化成求一条从面额s到0的满足题意的路径，因为硬币面额不可能是负的或0，所以这也是一个DAG问题。