CF 653 D - Delivery Bears
問題
問題概要
街で熊を雇って運び屋業をすることにした.街は頂点が個,辺が本ある有向グラフとして表される.各辺には耐えられる重量が決まっている.1回の配達を,1頭の熊が頂点から頂点へ運搬する際のパスとして表現する.
今,熊が頭いる.公平性のために,熊は同じ重さの荷物を持ち途中で休んだりせず目的地へ向かう.ただし,熊は自由にルートを選択できる.この時に運べる荷物の重量の合計の最大値をもとめよ.
- 自己ループや多重辺は無く,頂点から頂点へのルートが最低限1つはあることが保証されている.
アイデア
問題では合計を答えることになっているが,1頭が持つべき荷物の重さについて求めていくことにする.すると,問題に対しての答えはとなるので,これを答えれば良い.この問題では,ある値を境界として運搬が可能である重さと,不可能である重さに分かれることは簡単に想像できる.このような状況に対して有効なのは二分探索である.を二分探索によって求める方針を考えよう.
このように問題が置き換わると,「1頭に重さの荷物をもたせた時に運搬可能であるか」を判定する問題になる.この判定問題を解くために,最大フローを使う.ただし,そのままこのグラフを利用するのではなく,ちょっとした変換を行う.それは辺の容量を熊1頭を1単位とすることである.つまり熊をフローとして考える.今,熊1頭につき重さの荷物を持っているわけであるから,各辺を一度に熊が通る事のできる数はの小数点以下切り捨ての値となる.このように辺を変換したグラフの最大フローを求め,その値が以上だったらは実現可能であると判定することが出来る.今回はももそんなに大きくないので,二分探索が収束するまでその都度フローをつくることで十分間に合う.
実装(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を実装したい.