Editorial for 流量 (APCS 2021-01 中級)

簡潔題意

有 \(n\) 台伺服器與 \(m\) 座城市，\(Q[i][j]\) 是伺服器 \(i\) 要傳給城市 \(j\) 的流量。每個方案指定每台伺服器放在哪座城市；計費時先把「起點城市與終點城市都相同」的流量加總成 \(F[u][v]\)，再一對一對計費：同城（\(u = v\)）每單位 \(1\) 元；跨城且 \(F[u][v] \le 1000\) 每單位 \(3\) 元；跨城超過 \(1000\) 時，前 \(1000\) 單位仍是每單位 \(3\) 元、超過的部分才是每單位 \(2\) 元（即 \(3000 + 2(F[u][v] - 1000)\) 元）。輸出 \(k\) 個方案中的最低總費用（\(1 \le n, m, k \le 50\)、\(0 \le Q[i][j] \le 1000\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(20\) 分）：\(n = 1\) 且 \(k = 1\)。
  • 子題組 2（\(30\) 分）：\(n = 1\)。
  • 子題組 3（\(50\) 分）：無額外限制。

先拿下子題組 1、2（50 分）：一台伺服器，折扣根本用不到

\(n = 1\) 時只有一台伺服器。它放在城市 \(c\)，那麼傳到 \(c\) 的那一筆是同城、每單位 \(1\) 元，傳到其他城市的每一筆都是跨城、每單位 \(3\) 元。更好的是：每個「起點終點都相同」的流量就只有 \(Q[0][j]\) 一筆，而題目保證 \(Q[i][j] \le 1000\)——「彙總後超過 \(1000\)」在 \(n = 1\) 時根本不會發生，整段折扣規則可以先放著不管。

把 \(m\) 個流量讀進一維陣列（6.1），對每個方案算一次費用、用擂台記最小值。擂台的初值不能用 \(0\)——費用可能真的是 \(0\)（全部流量都是 \(0\)），所以「還沒有方案上台」的記號要用值域外的 \(-1\)：

#include <iostream>
using namespace std;

const int MAX_M = 50;

int main() {
    int n, m, k;
    cin >> n >> m >> k;                     // 子題組 1、2 保證 n 一定是 1
    int q[MAX_M];
    for (int j = 0; j < m; j++) {
        cin >> q[j];
    }
    int best = -1;                          // 擂台：目前最低費用（-1＝還沒有方案上台）
    for (int i = 0; i < k; i++) {
        int c;
        cin >> c;                           // 唯一一台伺服器放在城市 c
        int cost = 0;
        for (int j = 0; j < m; j++) {
            if (j == c) {
                cost += q[j];               // 同城：每單位 1 元
            } else {
                cost += 3 * q[j];           // 跨城：每筆最多 1000，折扣用不到
            }
        }
        if (best == -1 || cost < best) {
            best = cost;
        }
    }
    cout << best << endl;
}

注意：兩個範例的 \(n\) 都不是 \(1\)，這份程式對兩個範例都會 WA——這是正常的，它本來就只負責 \(n = 1\)。想驗它，用自測表的第 1 列自己做一筆 \(n = 1\) 的測資。逐筆給分之下，子題組 1、2 的 \(50\) 分穩穩到手。

從 50 分到 100 分：先彙總、再計費

多台伺服器可能放在同一座城市。題目說得很清楚：起點與終點都相同的流量要先加總，門檻 \(1000\) 是對加總後的 \(F[u][v]\) 判斷的，不是對單筆 \(Q[i][j]\) 判斷。所以計費前先把一張 \(m \times m\) 的表填出來——二維陣列不只能當地圖，這裡它是一張「起點 × 終點」的統計表（13.1；用陣列收集資訊的一維版思想在 6.7）：伺服器 \(i\) 在城市 city[i]，它傳往城市 \(j\) 的流量就累加進 flow[city[i]][j]。

彙總完掃過所有 \((u, v)\)，三條費率照著題目抄；記得 \(3000 + 2(f - 1000)\) 的 \(3000\) 是前 \(1000\) 單位乘 \(3\) 的錢。每個方案都要把 flow 重新歸零再彙總——上一個方案的流量留在表裡，這個方案的費用就被灌水了。

要不要 long long？估一下（2.9）：全部流量總和最多 \(50 \times 50 \times 1000 = 2500000\)，每單位最貴 \(3\) 元，一個方案的總費用頂多 \(7500000\)，離 int 上限 \(21\) 億遠得很；費用也不可能是負的，下界不用煩惱——int 夠。不想估就全用 long long，兩種都對。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 50;

int q[MAX_N][MAX_N];      // q[i][j]＝伺服器 i 要傳到城市 j 的流量
int flow[MAX_N][MAX_N];   // flow[u][v]＝這個方案中，城市 u 傳到城市 v 的總流量
int city[MAX_N];          // city[i]＝這個方案把伺服器 i 放在哪座城市

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> q[i][j];
        }
    }

    int best = -1;                          // 擂台：目前最低費用（-1＝還沒有方案上台）
    for (int p = 0; p < k; p++) {
        for (int i = 0; i < n; i++) {
            cin >> city[i];
        }

        for (int u = 0; u < m; u++) {       // 每個方案都要從全 0 重新彙總
            for (int v = 0; v < m; v++) {
                flow[u][v] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                flow[city[i]][j] += q[i][j];   // 起點＝伺服器所在城市，終點＝城市 j
            }
        }

        int cost = 0;
        for (int u = 0; u < m; u++) {
            for (int v = 0; v < m; v++) {
                int f = flow[u][v];
                if (u == v) {
                    cost += f;                        // 同城：每單位 1 元
                } else if (f <= 1000) {
                    cost += 3 * f;                    // 跨城、沒超過 1000：每單位 3 元
                } else {
                    cost += 3000 + 2 * (f - 1000);    // 前 1000 單位仍是 3 元，超過的部分才是 2 元
                }
            }
        }
        if (best == -1 || cost < best) {
            best = cost;
        }
    }
    cout << best << endl;
}

速度不用擔心：一個方案彙總 \(n \times m\) 次、計費 \(m \times m\) 次，\(k\) 個方案總共 \(50 \times (2500 + 2500) = 250000\) 次上下。

測過再交：範例測不到 \(n = 1\)，也測不到門檻上的 \(1000\)

範例 1 所有彙總後的流量都沒超過 \(1000\)，折扣寫錯它完全不知道；範例 2 有超過 \(1000\) 的彙總流量，能抓到一部分計費錯誤，但它的第一個方案剛好就是最便宜的——「只算第一個方案」的程式範例 2 照樣過。剩下的缺口自己補：

輸入 正確輸出 這一筆在測什麼
1 2 1／700 700／0 2800 \(n = 1\)：\(700 + 3 \times 700\)。子題組版唯一能跑的驗收（兩個範例它都跑不了）
2 2 1／500 500／500 500／0 0 4000 彙總恰好 \(1000\)：跨城那筆 \(3 \times 1000 = 3000\)，而 \(3000 + 2 \times 0\) 也是 \(3000\)——門檻上兩條規則同價，判斷寫 <= 或 < 都對；同城那筆 \(1000\) 元
2 2 1／600 600／600 600／0 0 4600 彙總 \(1200\)：同城照樣每單位 \(1\) 元（\(1200\) 元，不套折扣式），跨城 \(3000 + 2 \times 200 = 3400\)。每台伺服器分開計費的程式印 4800、超過 \(1000\) 整批乘 \(2\) 的程式印 3600
2 2 2／900 0／900 0／0 1／0 0 1800 第二個方案才是最小值：只算第一個方案、或 flow 沒歸零的程式都印 3600

四筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 每台伺服器分開計費、費用再相加：折扣門檻是對「彙總後」的流量判斷的——兩台各傳 \(600\) 的伺服器同城時合計 \(1200\)，有 \(200\) 單位該打折。範例 1 過、範例 2 抓到（印 13880）；自測表第 3 列印 4800。
  • 超過 \(1000\) 就整批每單位 \(2\) 元：前 \(1000\) 單位仍是 \(3\) 元，\(3000\) 那一項不能丟。範例 1 過、範例 2 抓到（印 10470）；自測表第 3 列印 3600。
  • 同城也套跨城費率：\(u = v\) 每單位就是 \(1\) 元，沒有 \(3\) 元也沒有折扣。範例 1 就抓到（印 327）。
  • 只按終點彙總成一維（不分起點）：不同起點的流量不能合併，而且「哪筆是同城」的資訊也一起丟了。範例 1 就抓到（印 327）。
  • 每個方案開始前沒把 flow 歸零：後面的方案疊著前面的流量，費用被灌水。範例 1 抓到（印 257）；自測表第 4 列印 3600。
  • 只算第一個方案、忘了取最小值：範例 1 抓到（印 257）；範例 2 剛好過——它的第一個方案正好最便宜。自測表第 4 列印 3600。