骨牌堆疊 題解|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\) 筆。