裏紙

ほぼ競プロ、たまに日記

CF 653 D - Delivery Bears

問題

Problem - D - Codeforces

問題概要

街で熊を雇って運び屋業をすることにした.街は頂点がn個,辺がm本ある有向グラフとして表される.各辺には耐えられる重量c_iが決まっている.1回の配達を,1頭の熊が頂点1から頂点nへ運搬する際のパスとして表現する.

今,熊がx頭いる.公平性のために,熊は同じ重さの荷物を持ち途中で休んだりせず目的地へ向かう.ただし,熊は自由にルートを選択できる.この時に運べる荷物の重量の合計の最大値をもとめよ.

  • 2 \le n \le 50
  • 1 \le m \le 500
  • 1 \le x \le 100000
  • 1 \le c_i \le 1000000
  • 自己ループや多重辺は無く,頂点1から頂点nへのルートが最低限1つはあることが保証されている.

イデア

問題では合計を答えることになっているが,1頭が持つべき荷物の重さwについて求めていくことにする.すると,問題に対しての答えはw*xとなるので,これを答えれば良い.この問題では,ある値を境界として運搬が可能である重さと,不可能である重さに分かれることは簡単に想像できる.このような状況に対して有効なのは二分探索である.wを二分探索によって求める方針を考えよう.

このように問題が置き換わると,「1頭に重さwの荷物をもたせた時に運搬可能であるか」を判定する問題になる.この判定問題を解くために,最大フローを使う.ただし,そのままこのグラフを利用するのではなく,ちょっとした変換を行う.それは辺の容量を熊1頭を1単位とすることである.つまり熊をフローとして考える.今,熊1頭につき重さwの荷物を持っているわけであるから,各辺を一度に熊が通る事のできる数は\frac{c_i}{w}の小数点以下切り捨ての値となる.このように辺を変換したグラフの最大フローを求め,その値がx以上だったらwは実現可能であると判定することが出来る.今回はnmもそんなに大きくないので,二分探索が収束するまでその都度フローをつくることで十分間に合う.

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

//型設定(int?long?ll?)
typedef ll ff_t;

//辺を表す構造体(行き先、容量。逆辺)
struct edge {ff_t to, cap, rev;};

//ノードの数
const ff_t MAX_V = 50;
//LIMIT
const ff_t FF_INF = 1234567890123LL;
//グラフの隣接リスト表現
vector<edge> G[MAX_V];
//DFSですでに調べたかのフラグ
bool used[MAX_V];

//fromからtoへ向かう容量capの辺をグラフに追加する
void add_edge(ff_t from, ff_t to, ff_t cap){
    G[from].push_back((edge){to, cap, G[to].size()});
    G[to].push_back((edge){from, 0, G[from].size()-1});
}

//増加パスを探す
ff_t ff_dfs(ff_t v, ff_t t, ff_t f){
    if(v==t) return f;
    used[v]=true;

    for(ff_t i=0; i<G[v].size(); ++i){
        edge &e=G[v][i];
        if(!used[e.to] && e.cap>0){
            ff_t d = ff_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;
}

//sからtへの最大流を求める
ff_t max_flow(ff_t s, ff_t t){
    ff_t flow=0;
    for(;;){
        memset(used,0,sizeof(used));
        ff_t f = ff_dfs(s,t,FF_INF);
        if(f==0) return flow;
        flow+=f;
    }
}

int main()
{
    int n,m,x;
    cin >>n >>m >>x;
    vector<int> a(m),b(m),c(m);
    rep(i,m)
    {
        scanf(" %d %d %d", &a[i], &b[i], &c[i]);
        --a[i];
        --b[i];
    }

    double l=0, r=1e8;
    rep(times,100)
    {
        //初期化
        fill(used,used+MAX_V,false);
        rep(i,MAX_V) G[i].clear();

        double mid=(l+r)/2;
        //辺を作成
        rep(i,m)
        {
            double tc=c[i]/mid;
            add_edge(a[i],b[i],(ll)tc);
        }

        if(max_flow(0,n-1)>=x) l=mid;
        else r=mid;
    }
    printf("%.10lf\n", l*x);
    return 0;
}

とりあえず今持ってる最大フローを使った.MaxFlowもクラス化したいんだけど,まだできてない...蟻本をもうちょっと読み進めて,どうせならDinicを実装したい.