UVA11613 Acme Corporation

题意

翻译已经很清楚了。

思路

看到这种求限制下的最值的问题，而且数据范围还比较小，我们不难想到费用流。但是这道题要求的是最大利润，那么我们可以将边权全部乘以 \(-1\)，这样就可以通过求最小费用来求得最大利润。此时我们求的也就是亏钱的最小值，只不过这个值可以是负的，表示盈利。

为了方便，我们约定源点为 \(s\)，汇点为 \(t\)。

首先，我们可以将第 \(i\) 个月拆成两个点：\(i\) 和 \(i + N\)，其中我们用 \(i\) 来表示成本，\(i + N\) 来表示销售额。然后从 \(s\) 向 \(i\) 引一条容量为 \(n_i\)，费用为 \(m_i\) 的边，表示该月能够生产 \(n_i\) 件物品，每一件的成本为 \(m_i\)。再从 \(i + N\) 向 \(t\) 引一条容量为 \(s_i\)，费用为 \(-p_i\) 的边，表示该月能够出售 \(s_i\) 件物品，每一件的售价为 \(p_i\)。

然后我们再来处理储存物品的问题。对于每一个 \(j \in [0, e_i]\)，我们从 \(i\) 向 \(i + j + N\) 引一条边，其容量为 \(+\inf\)，费用为 \(W \times j\)，表示第 \(i\) 个月能够以 \(W \times j\) 的代价将物品储存至第 \(i + j\) 个月。其实这里边的容量取 \(n_i\) 就可以了，但是为了方便，我取了正无穷。

然后这张图就建好了。可以看出这张图是不可能存在负环的，那么我们将边权取相反数的做法就没有问题。

但是此时还有一个问题：每个月不一定非得生产 \(n_i\) 件物品，也就是说当利润最大时，对应的流可以不是满流。那么这个问题也就不是普通的 MCMF 问题，而是最大费用任意流问题。

处理方法也很简单，对于普通的连续最短路 MCMF，我们只需做这么一个变动：如果此次增广的费用为正，也就是亏了钱时，我们直接 break 就好了，因为此时你无论再怎么增广，费用都始终为正，也就是不可能再赚钱的。

代码

/**
 * @file    UVA11613 Acme Corporation.cpp
 * @author  ForgotDream
 * @brief   最大费用任意流
 * @date    2023-03-09
 */
#include <bits/stdc++.h>

using i64 = long long;

static const int INF = 0x3f3f3f3f;
struct MCMF {
  struct Edge {
    int from, to;
    i64 cap, cost;
    Edge(int u, int v, i64 cap, i64 cost) 
      : from(u), to(v), cap(cap), cost(cost) {}
  };
  static const i64 INF = 1e18;
  int n, s, t;
  std::vector<Edge> edge;
  std::vector<std::vector<int>> e;
  std::vector<int> cur;
  std::vector<i64> dis;
  std::vector<bool> vis;
  
  MCMF(const int &n) {
    this->n = n;
    e.resize(n);
    cur.resize(n);
    dis.resize(n);
    vis.resize(n);
    return;
  }

  bool spfa(int s, int t) {
    std::fill(dis.begin(), dis.end(), INF);
    std::fill(vis.begin(), vis.end(), false);
    std::fill(cur.begin(), cur.end(), 0);
    std::queue<int> q;

    q.push(s);
    dis[s] = 0;
    vis[s] = true;

    while (!q.empty()) {
      int u = q.front();
      q.pop();
      vis[u] = false;
      for (int i : e[u]) {
        int v = edge[i].to;
        if (edge[i].cap && dis[v] > dis[u] + edge[i].cost) {
          dis[v] = dis[u] + edge[i].cost;
          if (!vis[v]) {
            vis[v] = true;
            q.push(v);
          }
        }
      }
    }

    return dis[t] != INF;
  }

  i64 dfs(int u, i64 flow, i64 &minCost) {
    if (u == t || flow == 0) {
      return flow;
    }
    i64 res = 0, tmp;
    vis[u] = true;
    for (int &i = cur[u]; i < e[u].size(); i++) {
      Edge &curEdge = edge[e[u][i]];
      if (!vis[curEdge.to] && dis[curEdge.to] == dis[u] + curEdge.cost && 
          (tmp = dfs(curEdge.to, std::min(curEdge.cap, flow), minCost)) > 0) {
        minCost += tmp * curEdge.cost;
        curEdge.cap -= tmp;
        edge[e[u][i] ^ 1].cap += tmp;
        res += tmp;
        flow -= tmp;
        if (flow == 0) {
          break;
        }
      }
    }
    vis[u] = false;
    return res;
  }

  void add(int u, int v, i64 cap, i64 cost) {
    edge.emplace_back(u, v, cap, cost);
    edge.emplace_back(v, u, 0, -1 * cost);

    e[u].push_back(edge.size() - 2);
    e[v].push_back(edge.size() - 1);

    return;
  }

  std::pair<int, i64> solve(int s, int t) {
    int flow = 0;
    i64 cost = 0, lst = 0;
    this->s = s;
    this->t = t;
    while (spfa(s, t)) {
      lst = cost;
      flow += dfs(s, INF, cost);
      if (cost > lst) {
        break;
      }
    }
    return std::make_pair(flow, lst);
  }
};

void solve(int no) {
  int N;
  i64 W;
  std::cin >> N >> W;
  MCMF solver(2 * N + 50);
  int S = 0, T = 2 * N + 1;
  for (int i = 1; i <= N; i++) {
    i64 m, p;
    int n, s, e;
    std::cin >> m >> n >> p >> s >> e;
    for (int j = 0; i + j <= N && j <= e; j++) {
      solver.add(i, i + j + N, INF, W * j);
    }
    solver.add(S, i, n, m);
    solver.add(i + N, T, s, -1 * p);
  }
  std::cout << "Case " << no << ": " << -1 * solver.solve(S, T).second << "\n";
  return;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int t;
  std::cin >> t;

  for (int i = 1; i <= t; i++) {
    solve(i);
  }

  return 0;
}