時間限制 1000 ms ・ 記憶體限制 256 MB
題目描述
每張骨牌有方向 a_i → b_i 與權重 w_i。骨牌不能翻轉；若前一張的終點等於後一張的起點，便可接在一起，每張最多用一次。所有起點 a_i 各不相同，所有終點 b_i 也各不相同。請選至少一張骨牌排成合法接龍，使權重總和最大；可以只取某條鏈或環中的一段。
輸入格式
第一行為 n、m，1 ≤ n ≤ 400000，1 ≤ m ≤ 300000，m ≤ n。接著 m 行各為 a_i、b_i、w_i，1 ≤ a_i,b_i ≤ n，−1000 ≤ w_i ≤ 1000。
輸出格式
輸出最大權重總和。
範例測資
範例輸入 1
10 7 2 7 4 9 3 6 3 1 5 7 4 1 8 2 9 1 6 10 4 8 4
範例輸出 1
21
範例輸入 2
18 12 14 6 7 7 1 -9 18 15 -9 15 2 2 12 13 1 2 9 9 10 18 8 5 7 8 4 5 -1 3 14 4 17 4 9 1 17 -1
範例輸出 2
16
請先登入後再提交程式碼
討論與題解
載入討論區…