回『IOI/APCS』
s224. 2. 骨牌堆疊
標籤 :
通過比率: 0人/ 0人 (0%) [非即時]
評分方式：
Tolerant

最近更新 : 2026-03-17 12:41

內容

題目建置中，歡迎透過表單完善題目。

https://forms.gle/zYDuZnVvweiM3DTC6

---

你有 $m$ 張骨牌。每張骨牌可以用一個三元組 $(a_i, b_i, w_i)$ 表示，代表這張骨牌是從數值 $a_i$ 連接到 $b_i$，其權重為 $w_i$。

若一張骨牌的後端點與另一張骨牌的前端點相同，則這兩張骨牌可以接在一起。例如：骨牌 $a \to b$ 可以接上 $b \to c$。

規則如下：

  1. 骨牌不可翻轉（$a \to b$ 不能當作 $b \to a$ 使用）。

  2. 每張骨牌最多只能使用一次。

  3. 題目保證：所有的 $a_i$ 互不相同，且所有的 $b_i$ 互不相同。

請找出一條合法的骨牌序列，使得序列中所有骨牌的權重總和最大。

範例測資1：

以邊代表骨牌，路徑 9 -> 3 -> 5 -> 6 獲得的權重為 21。

範例測資2：

以邊代表骨牌，路徑 17 -> 4 -> 5 -> 7 獲得的權重為 16。

輸入說明

第一行包含兩個整數 $n, m$ ($1 \le n \le 4 \cdot 10^5, 1 \le m \le 3 \cdot 10^5, m \le n$)，分別代表數值的範圍與骨牌的數量。 接下來 $m$ 行，每行包含三個整數 $a_i, b_i, w_i$ ($1 \le a_i, b_i \le n, -1000 \le w_i \le 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
測資資訊：
記憶體限制： 64 MB
公開 測資點#0 (5%): 1.0s , <10M
公開 測資點#1 (5%): 1.0s , <10M
公開 測資點#2 (5%): 1.0s , <10M
公開 測資點#3 (5%): 1.0s , <10M
公開 測資點#4 (5%): 1.0s , <10M
公開 測資點#5 (5%): 1.0s , <10M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
提示 ：
標籤:
出處:
2026年3月 APCS 高級 [管理者： algo.seacow@ ... (演算法海牛) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」