APCS 110/01 實作題第二題題解 流量

2021-01-09 17:00:42 by Akira

題目敘述

有 \(N\) 個 server，\(M\) 個城市，每個 server 要向各城市傳輸資料。同城市內單位資料傳輸價格為 $1，不同城市間單位資料傳輸價格為 $3，但若傳輸量超過 1000 則超過的部分可享優惠價 $2。(所有城市間的單向 pair 分開計算)

今有 \(K\) 個把 server 放在各城市的方案，問當中最划算的方案之價格。

輸入格式

\[
\begin{matrix}
N & M & K \\
s_{0,0} & s_{0,1} & ... & s_{0,M-1} \\
s_{1,0} & s_{1,1} & ... & s_{1,M-1} \\
... \\
s_{N-1,0} & s_{N-1,1} & ... & s_{N-1,M-1} \\
p_{0,0} & p_{0,1} & ... & p_{0,N-1} \\
p_{1,0} & p_{1,1} & ... & p_{1,N-1} \\
... \\
p_{K-1,0} & p_{K-1,1} & ... & p_{K-1,N-1} \\
\end{matrix}
\]

\(N, M, K \le 50\)

\(s_{i,j}\) 為 server #i 要向 城市 #j 傳送多少資料

\(p_{i,j}\) 為第 i 個方案打算把 server #j 放到第幾個城市 (\(0 \le p_{i,j} < M\))

保證答案不超過 \(10^8\)

輸出格式

印出一個數字：最佳方案的花費

---

題解

直接算

C++ 參考解答

#include <climits>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int NMAX = 50;
const int MMAX = 50;

int S[NMAX][MMAX];
int A[MMAX][MMAX];

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 >> S[i][j];
    }
  }
  int ans = INT_MAX;
  for (int k = 0; k < K; k++) {
    memset(A, 0, sizeof(A));
    for (int i = 0; i < N; i++) {
      int p;
      cin >> p;
      for (int j = 0; j < M; j++) A[p][j] += S[i][j];
    }
    int sum = 0;
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < M; j++) {
        if (i == j) {
          sum += A[i][j];
        } else if (A[i][j] <= 1000) {
          sum += A[i][j] * 3;
        } else {
          sum += A[i][j] * 2 + 1000;
        }
      }
    }
    ans = min(ans, sum);
  }
  cout << ans << endl;
  return 0;
}

---

[題解] [APCS] [APCS 110/01]