骨牌堆疊 題解|APCS 2026 年 3 月高級 第 2 題
前置知識
這題的核心是最大連續和,下面的講解直接把它當成已知,沒讀過的先讀:
- 非空的最大連續和:NTUCPC Guide〈枚舉〉的例題 CSES 1643「所有非空區間之中,最大的總和」(固定右界、記下看過的最小前綴和),吳邦一《AP325》第 4 章的 P-4-13「最大連續子陣列」也是同一個問題(站上題目 ap325p413)。下面用的是另一種同樣 \(O(n)\) 的寫法:「以第 \(i\) 項結尾的最大和」等於「只選第 \(i\) 項」與「接在前一項的最佳值後面」取大。
簡潔題意
\(m\) 張骨牌,第 \(i\) 張寫著 \(a_i \to b_i\) 與分數 \(w_i\)。選至少一張排成一列,前一張的 \(b\) 要等於後一張的 \(a\),不能翻轉、每張最多用一次。求分數總和的最大值,就算是負的也必須選(\(1 \le n \le 4 \times 10^5\),\(1 \le m \le \min(n, 3 \times 10^5)\),數字都在 \(1 \sim n\),\(-1000 \le w_i \le 1000\);所有 \(a_i\) 互異、所有 \(b_i\) 互異)。(APCS 逐筆給分。)
骨牌就是有向邊,圖只會是鏈和環
把每張骨牌看成有向邊 \(a_i \to b_i\)。每個數字最多當一次 \(a\)、最多當一次 \(b\),所以每個點最多一條出邊、一條入邊——整張圖拆開來只有兩種形狀:一條鏈(從沒有入邊的點出發一直走到底)和一個環。能排成一列的骨牌,就是鏈或環上的一段連續的邊。
走訪方式:先從每個「有出邊、沒有入邊」的點出發沿著出邊走到底,走過的邊標記起來;剩下還沒走過、又有出邊的點一定在環上,從它出發走一圈回到起點。
鏈:非空的最大連續和
把鏈上的分數照順序排成一列,答案就是最大連續和,而且不能是空的(至少選一張):以第 \(i\) 張結尾的最佳值取 \(\max(w_i,\ \text{前一張的最佳值} + w_i)\),全部取最大。初始值不能設成 \(0\),否則全部是負數時會選到空集合。
環:多一種「繞過起點」的選法
環上的一段連續骨牌有兩種:不跨過我們出發的起點(就是上面的最大連續和),或者跨過起點——這種選法等於整圈都選、再扣掉中間不選的一段,所以同時算「非空最小連續和」,用總和減掉它。
一個細節:整圈都是負數時,最小連續和就是整圈,「總和減最小連續和」會變成 \(0\),等於什麼都不選——不合法。所以只有當最大連續和 \(\ge 0\) 時才採用這個值(此時它頂多等於 \(0\),不會比正確答案好)。
每條邊走一次,時間 \(O(n + m)\)。答案最大 \(3 \times 10^5 \times 1000 = 3 \times 10^8\),int 放得下。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 400000;
int n, m;
int next_of[MAX_N + 1]; // next_of[a] = b:有一張骨牌 a -> b;0 表示 a 沒有往外的骨牌
int weight_of[MAX_N + 1]; // 那張骨牌的分數
int indegree[MAX_N + 1]; // 有幾張骨牌以這個數字為 b
bool visited[MAX_N + 1];
int answer;
// 從 start 開始沿著骨牌一直走,把走過的每張骨牌的分數排成一列,算非空最大連續和。
// 走回 start 就表示這是一個環,再多算「總和減最小連續和」。
void walk(int start) {
int u = start;
int sum = 0; // 這一條的總分
int best_end = 0, worst_end = 0; // 以目前這張骨牌結尾的最大/最小連續和
int best = -1000000000, worst = 1000000000;
while (next_of[u] != 0 && !visited[u]) {
visited[u] = true;
int w = weight_of[u];
best_end = max(w, best_end + w);
worst_end = min(w, worst_end + w);
best = max(best, best_end);
worst = min(worst, worst_end);
sum += w;
u = next_of[u];
}
answer = max(answer, best);
// 走回起點 = 環。可以跨過起點的選法 = 全部減掉中間捨棄的一段(捨棄的一段非空)。
// 全環都是負數時 best < 0,sum - worst 會變成「全部捨棄」的 0,不能採用。
if (u == start && best >= 0) answer = max(answer, sum - worst);
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
next_of[a] = b;
weight_of[a] = w;
indegree[b]++;
}
answer = -1000000000;
// 先從「沒有骨牌接進來」的數字出發,這些是鏈
for (int i = 1; i <= n; i++)
if (next_of[i] != 0 && indegree[i] == 0) walk(i);
// 剩下還沒走過、又有骨牌往外的數字,一定在環上
for (int i = 1; i <= n; i++)
if (next_of[i] != 0 && !visited[i]) walk(i);
cout << answer << '\n';
return 0;
}
測過再交:範例的答案都是正的
兩個範例的答案是 \(21\) 和 \(16\),都是正的。沒蓋到的:答案是負的、要跨過起點的環、整圈都是負數的環、只有一張的環,還有最大的輸入。有三種錯法兩個範例都會過(見常犯錯誤),第 1~3 列就是抓它們的。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
2 1 / 1 2 -5 |
-5 |
只有一張、分數是負的:還是必須選 |
3 3 / 1 2 5 / 2 3 -10 / 3 1 5 |
10 |
環 \(1 \to 2 \to 3 \to 1\) 從 \(1\) 出發走一圈:最好的選法是 \(3 \to 1\)、\(1 \to 2\) 這兩張,跨過了起點 |
2 2 / 1 2 -3 / 2 1 -4 |
-3 |
整圈都是負數的環:只選分數最高的一張 |
1 1 / 1 1 7 |
7 |
只有一張的環(\(1 \to 1\)) |
| 用程式造:\(n = 4 \times 10^5\)、\(m = 3 \times 10^5\),一個大環 \(1 \to 2 \to \cdots \to 300000 \to 1\),分數都是 \(1000\) | 300000000 |
最大的輸入:整圈全選 |
五筆都親眼看過正確,這題就穩了。
常犯錯誤
- 最大連續和的初始值設 \(0\)(允許空集合):範例全過;自測表第 1 列會印
0,本站 \(20\) 筆掛 \(6\) 筆。 - 環的「總和減最小連續和」沒擋整圈都是負數的情況:範例全過;自測表第 3 列會印
0(整圈都扣掉),本站 \(20\) 筆掛 \(5\) 筆。 - 把環當成鏈,只從某一點切開算一次最大連續和:跨過切點的選法漏掉了。範例全過;自測表第 2 列會印
5,本站 \(20\) 筆掛 \(6\) 筆。