骨牌堆疊 (APCS 2026-03 高級)
2.0s 256M第 \(i\) 張骨牌記有有向接頭 \(a_i\to b_i\) 與分數 \(w_i\)。選擇至少一張骨牌排成一列,前張的 \(b\) 必須等於後張的 \(a\)。骨牌不能翻轉,每張至多使用一次。求分數總和的最大值,即使它是負數也必須選牌。
輸入格式
第一行為 \(n,m\),接著 \(m\) 行各有 \(a_i,b_i,w_i\)。
輸出格式
輸出最高總分。
資料範圍
\(1\le n\le400000\),\(1\le m\le\min(n,300000)\);\(1\le a_i,b_i\le n\);\(-1000\le w_i\le1000\)。所有 \(a_i\) 互異,所有 \(b_i\) 互異。
評分說明
每筆計分測資獨立計分,每筆 5 分,共 100 分;範例不計分。
範例輸入 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
題目來源
APCS 2026 年 3 月高級實作題第 2 題。
官方未公布題本,題敘參考 ZeroJudge s224「骨牌堆疊」 上的重建版整理,細節可能與正式試題有出入。