Submission #132198

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
//#include <gmpxx.h> 
#include <iostream>
//#include <map>
#include <queue>
#include <unordered_map>
#include <utility>
#include <set>
#include <sstream>
#include <stack>
#include <string>
//#include <sys/time.h>
#include <vector>
using namespace std;
#define li          int64_t
#define rep(i, n)   for(li i = 0; i < ((li)(n)); ++i)
#define pb          push_back
#define sz(v)       ((li)((v).size()))
#define bit(n)      (((li)1)<<((li)(n)))
#define all(v)      (v).begin(), (v).end()
#define each(it, v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
#define MP          make_pair
#define F           first
#define S           second



template <class T> class MinCostFlow
{
public:
  void addEdge(int from, int dest, int capacity, T cost);
  void terminateNegativeLoop(); // This requires all negative loops to be touched.
  T minCostFlow(int flow_source, int flow_target, int flow);

  MinCostFlow(int vertex_num);
  MinCostFlow(){}

private:
  class Edge
  {
  public:
    int dest;
    int capacity;
    int reversed_index;
    T cost;
    
    Edge(int dest, int capacity, int reversed_index, T cost)
    {
      this->dest = dest;
      this->capacity = capacity;
      this->reversed_index = reversed_index;
      this->cost = cost;
    }
  };
  T negative_loop_cost;
  int vertex_num;
  std::vector<std::vector<Edge>> edges;
};

template <class T>
inline MinCostFlow<T>::MinCostFlow(int vertex_num)
{
  this->vertex_num = vertex_num;
  negative_loop_cost = 0;
  edges = std::vector<std::vector<Edge>>(vertex_num);
}

template <class T>
inline void MinCostFlow<T>::addEdge(int from, int dest, int capacity, T cost)
{
  Edge e0(dest, capacity, edges[dest].size(),  cost);
  Edge e1(from,        0, edges[from].size(), -cost);
  edges[from].push_back(e0);
  edges[dest].push_back(e1);
}

template <class T>
inline T MinCostFlow<T>::minCostFlow(int flow_source, int flow_target, int flow)
{
  std::vector<std::tuple<T, bool>> costs(vertex_num);
  T total = 0;
  std::vector<int> pre_v(vertex_num);
  std::vector<int> pre_e(vertex_num);
  while(0 < flow){
    for(int vertex = 0; vertex < vertex_num; ++vertex) costs[vertex] = std::make_tuple(0, false);
    costs[flow_source] = std::make_tuple(0, true);
    for(bool updated = true; updated;){
      updated = false;
      for(int vertex = 0; vertex < vertex_num; ++vertex){
        if(!std::get<1>(costs[vertex])) continue;
        for(int edge_index = 0; edge_index < edges[vertex].size(); ++edge_index){
          Edge &e = edges[vertex][edge_index];
          if(e.capacity == 0) continue;
          if(std::get<1>(costs[e.dest]) && std::get<0>(costs[e.dest]) <= std::get<0>(costs[vertex]) + e.cost) continue;
          costs[e.dest] = std::make_tuple(std::get<0>(costs[vertex]) + e.cost, true);
          pre_v[e.dest] = vertex;
          pre_e[e.dest] = edge_index;
          updated = true;
        }
      }
    }
    if(!std::get<1>(costs[flow_target])) return -1;
    int minimum_flow = flow;
    for(int vertex = flow_target; vertex != flow_source; vertex = pre_v[vertex]){
      minimum_flow = std::min(minimum_flow, edges[pre_v[vertex]][pre_e[vertex]].capacity);
    }
    flow -= minimum_flow;
    
    total += minimum_flow * std::get<0>(costs[flow_target]);
    for(int vertex = flow_target; vertex != flow_source; vertex = pre_v[vertex]){
      Edge &e = edges[pre_v[vertex]][pre_e[vertex]];
      e.capacity -= minimum_flow;
      edges[vertex][e.reversed_index].capacity += minimum_flow;
    }
  }
  return total + negative_loop_cost;
}

template <class T> 
void MinCostFlow<T>::terminateNegativeLoop()
{
  std::vector<int> pre_v(vertex_num);
  std::vector<int> pre_e(vertex_num);
  std::vector<int> used(vertex_num);
  std::vector<T> distances(vertex_num);

  while(true){
    int vertex_in_loop = -1;
    for(int i = 0; i < vertex_num; i++) used[i] = distances[i] = 0;
    for(int step = 0; step <= vertex_num; ++step){
      bool updated=false;
      for(int vertex = 0; vertex < vertex_num; ++vertex){
        for(int edge_index = 0; edge_index < edges[vertex].size(); ++edge_index){
          Edge &e = edges[vertex][edge_index];
          if(e.capacity == 0 || distances[e.dest] <= distances[vertex] + e.cost) continue;
          distances[e.dest] = distances[vertex] + e.cost;
          pre_v[e.dest] = vertex;
          pre_e[e.dest] = edge_index;
          vertex_in_loop = e.dest;
          updated = true;
        }
      }
      if(!updated) return;
    }

    for(; !used[vertex_in_loop]; vertex_in_loop = pre_v[vertex_in_loop]) used[vertex_in_loop] = true;
    
    T total_cost = 0;
    int minimum_capacity = edges[pre_v[vertex_in_loop]][pre_e[vertex_in_loop]].capacity;
    int cur = vertex_in_loop;
    do{
      total_cost += edges[pre_v[cur]][pre_e[cur]].cost;
      minimum_capacity = std::min(minimum_capacity, edges[pre_v[cur]][pre_e[cur]].capacity);
      cur = pre_v[cur];
    }while(cur != vertex_in_loop);

    negative_loop_cost += total_cost * minimum_capacity;
    
    cur = vertex_in_loop;
    do{
      Edge &e = edges[pre_v[cur]][pre_e[cur]];
      e.capacity -= minimum_capacity;
      edges[cur][e.reversed_index].capacity += minimum_capacity;
      cur = pre_v[cur];
    }while(cur != vertex_in_loop);
  }
}





int main()
{
  li pos[3] = {-100, 0, 100};
  li num[3];
  cin >> num[0] >> num[1] >> num[2];
  
  const li GETA = 300 * 3;
  const li MAX = GETA * 2;
  MinCostFlow<li> flow(MAX + 5);
  li source = MAX + 0;
  li target = MAX + 1;
  li boxes[3] = {MAX + 2, MAX + 3, MAX + 4};
  
  rep(i, MAX)rep(j, 3) flow.addEdge(boxes[j], i, 1, abs(pos[j] - (i - GETA)));
  rep(i, 3) flow.addEdge(source, boxes[i], num[i], 0);
  rep(i, MAX) flow.addEdge(i, target, 1, 0);
  
  cout << flow.minCostFlow(source, target, num[0] + num[1] + num[2]) << endl;
}

Submission Info

Judge Result