# 實作題 - 流量 - APCS - by Peter Wang
## 題目資訊
此題為2021.1測驗中的題目2
###### tags: `APCS`

## 題目敘述
有 n 個伺服器編號 0 到 n−1，以及 m 個城市編號 0 到 m−1，已知第 i 個伺服器要傳送到城市 j 的流量為 Q[i][j]。

工程師們在規劃每個伺服器應該要放在哪個城市，對於一個方案 c=(c1,c2,c3,…cn)，表示編號 i 的伺服器要放在城市 ci。

城市之間資料傳輸是需要費用的，若城市u 要傳送 f 的流量到城市 v，費用的計算方式如下：

若 u=v，每單位流量需要花 1 塊錢。
若 u≠v，小於等於 1000 的流量每單位要 3 塊錢，大於 1000 的部份每單位 2 塊錢。
若城市u 有多個伺服器都要傳送流量到城市 v，會先將這些起點終點相同的傳輸流量相加再計算花費。

工程師們總共提出了 k 種方案，請你找到花費最少的方案所需的費用。
### 輸入：
第一行包含三個整數 n,m,k。

接下來 n 行每行有 m 個整數，第 i 行的第 j 個數字為 Q[i][j]。

接下來有 k 行，每行有 n 個整數，表示一個方案。
### 輸出：
輸出費用最小的方案所需的花費。

## 解題思路
按照題目規則實作，雖然稍微有點複雜，不過最終都能解出來。

## 程式碼

#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;
}

## 資料來源
[zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=f606)

## 備註
>[name=PeterWang]
>[time=Thu, Aug 12, 2021 10:24 PM]