IndiaHacks 2016 D: Delivery Bears

Codeforces 競技プログラミング

問題

Problem - D - Codeforces

解法

最大フロー問題っぽい雰囲気を感じることができるが、単純にそのまま最大フローをしてもダメな理由は「クマが分裂できない」ためである。そこで、最大フローの各辺のcapacityにweightをそのまま代入するのではなく、「通ることの出来るクマの数」を代入することを考える。

クマ一人あたりの荷物をwとすると、通ることの出来るクマの数=weight/w となるので、二分探索でこのwを当てにいく。グラフが小さいので、何回も生成しても十分間に合う。

twitter.com

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template <typename T>
class MaximumFlow {
  struct edge_t {
    int to;
    T cap, rev;
    edge_t(int t, T c, T r) : to(t), cap(c), rev(r) {}
  };
  vector<vector<edge_t>> G;
  MaximumFlow() {}
  vector<bool> used;
  T dfs(int v, int t, T f) {
    if (v == t) return f;
    used[v] = true;
    for (edge_t &e : G[v]) {
      if (used[e.to] || e.cap <= 0) continue;
      T d = dfs(e.to, t, min(f, e.cap));
      if (d > 0) {
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
    return 0;
  }
  T INF;

 public:
  MaximumFlow(int N) {
    G.resize(N);
    INF = numeric_limits<T>::max();
  }
  void add_edge(int from, int to, T cap) {
    G[from].push_back(edge_t(to, cap, G[to].size()));
    G[to].push_back(edge_t(from, 0, G[from].size() - 1));
  }

  T maximum_flow(int s, int t) {
    T flow = 0;
    while (true) {
      used.assign(G.size(), false);
      T f = dfs(s, t, INF);
      if (f == 0) return flow;
      flow += f;
    }
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, M, X;
  cin >> N >> M >> X;
  vector<pair<int, int>> edges(M);
  vector<double> costs(M);
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b >> costs[i];
    a--, b--;
    edges[i] = {a, b};
  }

  const double EPS = 0.00000001;
  double high = 1000000000.0, low = 0.0;
  double prevh = high, prevl = low;
  while ((high - low) * X > EPS) {
    double mid = (high + low) / 2.0;
    MaximumFlow<ll> f(N);
    for (int i = 0; i < M; ++i) {
      ll cap = min((ll)(costs[i] / mid), (ll)X);
      f.add_edge(edges[i].first, edges[i].second, cap);
    }
    ll flow = f.maximum_flow(0, N - 1);
    if (flow >= X) {
      low = mid;
    } else {
      high = mid;
    }
    if (prevh == high && prevl == low) break;
    prevh = high, prevl = low;
  }
  printf("%.15f\n", (high + low) / 2.0 * X);
}