算法學習之路|有向無環圖（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問題。