Summary

This problem asks us to pair visitors with items appropriately at a flea market to maximize the total profit. This problem can be reduced to the “maximum weight bipartite matching problem” in graph theory, and can be solved efficiently using a minimum cost flow algorithm.

Analysis

1. Understanding the Problem

Each visitor can purchase at most one item, and each item can be sold to at most one visitor. The profit when item \(j\) is sold to visitor \(i\) is \(P_{i, j} = V_{i, j} - C_j\) yen. Since we do not make transactions with negative profit, we only consider pairs with \(P_{i, j} \geq 0\).

This is a maximum weight bipartite matching problem, where we want to form pairs (a matching) between the set of visitors and the set of items to maximize the total profit.

2. Difference from Simple Maximum Matching

We cannot simply find the “maximum matching” (i.e., making as many pairs as possible). This is because forcing more transactions might require including low-profit transactions that prevent high-profit ones, potentially reducing the overall profit.

For example, consider the following case: - Transaction A: Profit of \(100\) yen - Transaction B: Profit of \(10\) yen (however, cannot be done simultaneously with Transaction A)

In this case, rather than choosing a combination to make the number of transactions 2, it is better to set the number of transactions to 1 and only perform Transaction A to get a larger total profit. Therefore, we need to consider the “maximum profit when the number of transactions (flow) is \(f\)” for all possible \(f\), and choose the one that yields the maximum profit.

3. Reduction to Minimum Cost Flow

We convert the “maximization” problem into a “minimization” problem (minimum cost flow). In minimum cost flow algorithms (especially those using Dijkstra’s algorithm), edge costs must be non-negative. However, if we directly use the profit \(P_{i, j}\) as a negative cost ( \(-P_{i, j}\) ), negative edges will occur.

To address this, we introduce a sufficiently large constant \(U = 10^9\) (at least the maximum possible profit) and convert the profit \(P_{i, j}\) into a cost \(W_{i, j} = U - P_{i, j}\). Since \(P_{i, j} \geq 0\), the converted cost \(W_{i, j}\) is guaranteed to be non-negative (\(0 \leq W_{i, j} \leq U\)), making the minimum cost flow algorithm applicable.

When the number of transactions is \(f\): - Converted total cost: \(\sum (U - P_{i, j}) = f \times U - \sum P_{i, j}\) - Actual total profit: \(\sum P_{i, j} = f \times U - (\text{converted total cost})\)

In other words, if we find the minimum cost \(c\) for a transaction count \(f\), the maximum profit for that flow is calculated as \(f \times U - c\).

4. Determining the Number of Transactions \(f\)

Since the number of items is very small (\(M \leq 14\)), the maximum number of transactions (maximum flow) is at most \(14\). Using the slope function of ACL (AtCoder Library), we can obtain all the minimum costs \(c\) as the flow \(f\) varies from \(0\) to the maximum flow at once in the form of a piecewise linear function (slope). For all obtained \((f, c)\) pairs, we calculate \(f \times U - c\), and the maximum value among them will be the answer.

Algorithm

1. Network Construction

   • Prepare a source \(S\) and a sink \(T\).
   • For each visitor \(i\), add an edge from \(S \to i\) with capacity \(1\) and cost \(0\).
   • For each item \(j\), add an edge from \((N+j) \to T\) with capacity \(1\) and cost \(0\).
   • For each pair \((i, j)\) satisfying \(V_{i, j} \geq C_j\), add an edge from \(i \to (N+j)\) with capacity \(1\) and cost \(U - (V_{i, j} - C_j)\).

2. Running Minimum Cost Flow

   • Use ACL’s mcf_graph to get the slope from \(S\) to \(T\).

3. Calculating Maximum Profit

   • For each pair of (flow \(f\), cost \(c\)) obtained from slope, calculate the actual profit \(f \times U - c\), and find the maximum value among them.

Complexity

• Time Complexity: \(O(F \cdot E \log V)\)

  • Number of vertices \(V = N + M + 2 \approx 10^5\)
  • Number of edges \(E \leq N + M + N \times M \approx 2 \times 10^5\)
  • Maximum flow \(F \leq M \leq 14\)
  • Using the Successive Shortest Path algorithm, we perform at most \(F\) shortest path searches (Dijkstra’s algorithm). Since \(F \le 14\) is extremely small, this runs well within the time limit.

• Space Complexity: \(O(V + E)\)

  • This is the memory required to store the vertices and edges of the graph, which easily fits within the limit.

Key Implementation Points

• Magnitude of the Offset \(U\): Since the maximum value of \(V_{i, j} - C_j\) is \(10^9\), setting \(U = 10^9\) prevents the costs from becoming negative.

• Preventing Overflow: Calculations of costs and profits can reach up to around \(14 \times 10^9\), so it is necessary to use a 64-bit integer type (long long in C++) to avoid overflow.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/mincostflow>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> C(M);
    for (int j = 0; j < M; ++j) {
        cin >> C[j];
    }

    vector<vector<long long>> V(N, vector<long long>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> V[i][j];
        }
    }

    // グラフの構築
    // 超源点 S = 0
    // 来場者 i = 1 から N
    // 商品 j = N + 1 から N + M
    // 超終点 T = N + M + 1
    int S = 0;
    int T = N + M + 1;
    atcoder::mcf_graph<int, long long> g(N + M + 2);

    for (int i = 1; i <= N; ++i) {
        g.add_edge(S, i, 1, 0);
    }

    // 費用を非負にするためのオフセット U
    // 利益 P = V[i][j] - C[j] の最大値は 10^9 なので、U = 10^9 とすれば
    // 費用 U - P は常に非負となる。
    long long U = 1000000000LL;

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (V[i-1][j-1] >= C[j-1]) {
                long long P = V[i-1][j-1] - C[j-1];
                g.add_edge(i, N + j, 1, U - P);
            }
        }
    }

    for (int j = 1; j <= M; ++j) {
        g.add_edge(N + j, T, 1, 0);
    }

    // 最小費用流の slope を取得
    auto result = g.slope(S, T);

    long long max_profit = 0;
    for (auto [f, c] : result) {
        // 流量 f、費用 c のときの実際の利益
        long long profit = (long long)f * U - c;
        max_profit = max(max_profit, profit);
    }

    cout << max_profit << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.