fork download 
  1. /*
  2.     Problem: Minimum Cost to Satisfy Daily Demand Using Buy and Repair Options
  3.     Company Tag: Walmart
  4.  
  5.     Problem Statement:
  6.         A factory works for N days.
  7.  
  8.         On day i, it needs exactly R[i] widgets.
  9.  
  10.         A widget can be obtained in three ways:
  11.  
  12.             1. Buy a new widget
  13.                Cost = P
  14.  
  15.             2. Send a used widget for quick repair
  16.                It returns after M days
  17.                Cost = F
  18.  
  19.             3. Send a used widget for slow repair
  20.                It returns after Q days
  21.                Cost = S
  22.  
  23.         We need to satisfy demand every day with minimum total cost.
  24.  
  25.     Constraints:
  26.         1 <= N <= 2000
  27.         1 <= R[i] <= 10^7
  28.         1 <= P, M, F, Q, S <= 10^4
  29.         Q > M
  30.  
  31.     Simple Brute Force:
  32.         For every day, try all choices:
  33.             buy new,
  34.             quick repair,
  35.             slow repair,
  36.             store,
  37.             discard.
  38.  
  39.     Why Brute Force Fails:
  40.         The number of possible schedules becomes huge.
  41.  
  42.     Better Idea:
  43.         Model this as a minimum cost flow problem.
  44.  
  45.         Each widget is one unit of flow.
  46.  
  47.         For each day:
  48.             - clean widgets are used to satisfy demand
  49.             - after use, they become dirty
  50.             - dirty widgets can be repaired and reused later
  51.             - new widgets can be bought when needed
  52.  
  53.         We force exactly R[i] widgets to be used on day i.
  54.  
  55.     Dry Run:
  56.         N = 3
  57.         R = [1, 1, 1]
  58.         P = 10
  59.         M = 1, F = 3
  60.         Q = 2, S = 1
  61.  
  62.         Best plan:
  63.             Day 1: buy 1 widget        cost 10
  64.             Day 2: quick repaired one  cost 3
  65.             Day 3: quick repaired one  cost 3
  66.  
  67.         Total cost = 16
  68.  
  69.     Time Complexity:
  70.         Around O(flow augmentations * E log V)
  71.  
  72.     Space Complexity:
  73.         O(N)
  74. */
  75.  
  76. #include <bits/stdc++.h>
  77. using namespace std;
  78.  
  79. struct Edge {
  80.     int to;
  81.     int reverseIndex;
  82.     long long capacity;
  83.     long long cost;
  84. };
  85.  
  86. class MinCostFlow {
  87. public:
  88.     int nodeCount;
  89.     vector<vector<Edge>> graph;
  90.  
  91.     MinCostFlow(int n) {
  92.         nodeCount = n;
  93.         graph.assign(n, {});
  94.     }
  95.  
  96.     void addEdge(int from, int to, long long capacity, long long cost) {
  97.         Edge forward = {to, (int)graph[to].size(), capacity, cost};
  98.         Edge backward = {from, (int)graph[from].size(), 0, -cost};
  99.  
  100.         graph[from].push_back(forward);
  101.         graph[to].push_back(backward);
  102.     }
  103.  
  104.     pair<long long, long long> minCostMaxFlow(int source, int sink, long long requiredFlow) {
  105.         const long long INF = (1LL << 60);
  106.  
  107.         long long totalFlow = 0;
  108.         long long totalCost = 0;
  109.  
  110.         vector<long long> potential(nodeCount, 0);
  111.  
  112.         while (totalFlow < requiredFlow) {
  113.             vector<long long> distance(nodeCount, INF);
  114.             vector<int> parentNode(nodeCount, -1);
  115.             vector<int> parentEdge(nodeCount, -1);
  116.  
  117.             priority_queue<
  118.                 pair<long long, int>,
  119.                 vector<pair<long long, int>>,
  120.                 greater<pair<long long, int>>
  121.             > pq;
  122.  
  123.             distance[source] = 0;
  124.             pq.push({0, source});
  125.  
  126.             while (!pq.empty()) {
  127.                 pair<long long, int> current = pq.top();
  128.                 pq.pop();
  129.  
  130.                 long long currentDistance = current.first;
  131.                 int node = current.second;
  132.  
  133.                 if (currentDistance != distance[node]) {
  134.                     continue;
  135.                 }
  136.  
  137.                 for (int i = 0; i < (int)graph[node].size(); i++) {
  138.                     Edge &edge = graph[node][i];
  139.  
  140.                     if (edge.capacity <= 0) {
  141.                         continue;
  142.                     }
  143.  
  144.                     long long newDistance =
  145.                         distance[node] + edge.cost + potential[node] - potential[edge.to];
  146.  
  147.                     if (newDistance < distance[edge.to]) {
  148.                         distance[edge.to] = newDistance;
  149.                         parentNode[edge.to] = node;
  150.                         parentEdge[edge.to] = i;
  151.                         pq.push({newDistance, edge.to});
  152.                     }
  153.                 }
  154.             }
  155.  
  156.             if (distance[sink] == INF) {
  157.                 break;
  158.             }
  159.  
  160.             for (int i = 0; i < nodeCount; i++) {
  161.                 if (distance[i] < INF) {
  162.                     potential[i] += distance[i];
  163.                 }
  164.             }
  165.  
  166.             long long addFlow = requiredFlow - totalFlow;
  167.             int node = sink;
  168.  
  169.             while (node != source) {
  170.                 int previous = parentNode[node];
  171.                 int edgeIndex = parentEdge[node];
  172.  
  173.                 addFlow = min(addFlow, graph[previous][edgeIndex].capacity);
  174.                 node = previous;
  175.             }
  176.  
  177.             node = sink;
  178.  
  179.             while (node != source) {
  180.                 int previous = parentNode[node];
  181.                 int edgeIndex = parentEdge[node];
  182.  
  183.                 Edge &edge = graph[previous][edgeIndex];
  184.  
  185.                 edge.capacity -= addFlow;
  186.                 graph[node][edge.reverseIndex].capacity += addFlow;
  187.  
  188.                 totalCost += addFlow * edge.cost;
  189.  
  190.                 node = previous;
  191.             }
  192.  
  193.             totalFlow += addFlow;
  194.         }
  195.  
  196.         return {totalFlow, totalCost};
  197.     }
  198. };
  199.  
  200. int main() {
  201.     int N;
  202.     cin >> N;
  203.  
  204.     vector<long long> R(N);
  205.  
  206.     for (int i = 0; i < N; i++) {
  207.         cin >> R[i];
  208.     }
  209.  
  210.     long long P, M, F, Q, S;
  211.     cin >> P >> M >> F >> Q >> S;
  212.  
  213.     const long long INF_CAP = (1LL << 55);
  214.  
  215.     int cleanStart = 0;
  216.     int dirtyStart = N;
  217.  
  218.     int source = 2 * N;
  219.     int sink = 2 * N + 1;
  220.  
  221.     int superSource = 2 * N + 2;
  222.     int superSink = 2 * N + 3;
  223.  
  224.     int totalNodes = 2 * N + 4;
  225.  
  226.     MinCostFlow flow(totalNodes);
  227.  
  228.     vector<long long> balance(totalNodes, 0);
  229.  
  230.     auto addLowerBoundEdge = [&](int from, int to, long long lower, long long upper, long long cost) {
  231.         /*
  232.             Lower bound trick:
  233.             We force at least 'lower' flow through this edge
  234.             by adjusting the balance of both endpoints.
  235.         */
  236.         flow.addEdge(from, to, upper - lower, cost);
  237.  
  238.         balance[from] -= lower;
  239.         balance[to] += lower;
  240.     };
  241.  
  242.     for (int day = 0; day < N; day++) {
  243.         int cleanNode = cleanStart + day;
  244.         int dirtyNode = dirtyStart + day;
  245.  
  246.         // Buy a new clean widget for this day.
  247.         addLowerBoundEdge(source, cleanNode, 0, INF_CAP, P);
  248.  
  249.         // Exactly R[day] widgets must be used on this day.
  250.         addLowerBoundEdge(cleanNode, dirtyNode, R[day], R[day], 0);
  251.  
  252.         // After use, we may discard the dirty widget.
  253.         addLowerBoundEdge(dirtyNode, sink, 0, INF_CAP, 0);
  254.  
  255.         // Clean widgets can be stored for the next day.
  256.         if (day + 1 < N) {
  257.             addLowerBoundEdge(cleanNode, cleanStart + day + 1, 0, INF_CAP, 0);
  258.         }
  259.  
  260.         // Dirty widgets can also be kept and repaired later.
  261.         if (day + 1 < N) {
  262.             addLowerBoundEdge(dirtyNode, dirtyStart + day + 1, 0, INF_CAP, 0);
  263.         }
  264.  
  265.         // Quick repair makes a dirty widget clean after M days.
  266.         if (day + M < N) {
  267.             addLowerBoundEdge(dirtyNode, cleanStart + day + M, 0, INF_CAP, F);
  268.         }
  269.  
  270.         // Slow repair makes a dirty widget clean after Q days.
  271.         if (day + Q < N) {
  272.             addLowerBoundEdge(dirtyNode, cleanStart + day + Q, 0, INF_CAP, S);
  273.         }
  274.     }
  275.  
  276.     /*
  277.         This edge converts the network into a circulation problem.
  278.         It lets the flow balance out properly.
  279.     */
  280.     addLowerBoundEdge(sink, source, 0, INF_CAP, 0);
  281.  
  282.     long long requiredFlow = 0;
  283.  
  284.     for (int i = 0; i < totalNodes; i++) {
  285.         if (balance[i] > 0) {
  286.             flow.addEdge(superSource, i, balance[i], 0);
  287.             requiredFlow += balance[i];
  288.         } else if (balance[i] < 0) {
  289.             flow.addEdge(i, superSink, -balance[i], 0);
  290.         }
  291.     }
  292.  
  293.     pair<long long, long long> result =
  294.         flow.minCostMaxFlow(superSource, superSink, requiredFlow);
  295.  
  296.     cout << result.second << endl;
  297.  
  298.     return 0;
  299. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/lAo8Uw
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!