ホームに戻る
TopCoder の傾向と対策８（Ｃ＋＋編：最大フロー、最小カット、最小費用流）
１、最大フロー問題
最大フロー問題とは、
グラフの辺に通過できる最大量が決まっているとき、
ある頂点からある頂点に辺をつたってフローを流すとき、
最大どれだけの量を流せるかを求める問題。
やり方は、出発点から終点までの全探索をする。
それぞれの探索で流せる最大量を流す。
ある辺について最大量３であって量を２だけ流したときには、
最大量を２減らし、２だけ逆流できるようにする。
このように更新していけば、最大量を求めることができる。
以下はノード数6、エッヂ数8の最大フローのコード例。
#define V 6
#define E 8
int v[V][V];
int from[E] = {0,0,1,1,2,3,3,4};
int to[E] = {1,2,2,3,4,4,5,5};
int cap[E] = {3,3,2,3,2,4,2,3};
int flag[V];
int flow(int s, int e, int f){
if(s == e)return f;
flag[s] = 1;
for(int i = 0; i < V; i++){
if(v[s][i] > 0 && flag[i] == 0){
int d = flow(i, e, min(f, v[s][i]));
if(d > 0){
v[s][i] -= d;
v[i][s] += d;
return d;
}
}
}
return 0;
}
int main(){
for(int i = 0; i < V; i++){
for(int r = 0; r < V; r++){
v[i][r] = -1;
}
}
// グラフを作る
for(int i = 0; i < E; i++){
v[from[i]][to[i]] = cap[i];
v[to[i]][from[i]] = 0;
}
int ans = 0;
for(;;){
for(int i = 0; i < V; i++){
flag[i] = 0;
}
// 頂点 0 から 頂点 5 までを探索
int f = flow(0, 5, 100000000);
if(f == 0)break;
ans += f;
}
std::cout << ans << std::endl;
return 0;
}
２、２部マッチング
最大フロー問題は組み合わせにも応用できる。
例えば、グループＡとグループＢがあり、
グループＡの各要素は複数のグループＢの要素とペアを組める。
同様にグループＢの各要素もグループＡの要素とペアを組める。
このときにグループＡとＢでできる最大のペア数はいくつか？
このとき、スタートの頂点からすべてのグループＡに辺をつなぐ、
ペアになれるグループＡとグループＢを辺でつなぐ、
すべてのグループＢからゴールに辺をつなぐ。
辺の最大量はすべて１にする。
このときの最大量が最大のペア数と一致する。
特に、ペアを作る問題を２部マッチングという。
問題
四角い盤面に o と x が置かれている。
また、 . は何も置かれていないことを表す。
o の上下左右を x で囲うと o を . にできる。
o は隣合うことは無く、最初から x で囲われていない。
x を好きなだけ置いて . の数を最大にせよ。
例えば、以下のような盤面の場合、
...ox
.xox.
..x..
o..xx
x を1個置くことで、
..x.x
.x.x.
..x..
o..xx
にできる。
このとき . は 11→12 にできる。
左下の x は囲わないほうが良い。
..x.x
.x.x.
x.x..
.x.xx
となり . の数が1つ減る。
考え方
例えば、以下のような盤面の場合、
.xox.
x...x
o.o.o
x...x
.xox.
x を4個で o を5個囲うことができる。
よって、. を1個増やすことができる。
この判定をどのように行えば良いだろうか？
ここで o と隣り合う . をペアにすることを考える。
これを最大フローで最大化する。
すると、
.xAx.
x.A.x
BBoCC
x.D.x
.xDx.
以上のように A から D のペアができているので、
中央の o がペアを作ることができない。
o と o は条件により隣り合わないので、
この場合の中央の o は囲われていると判断して良い。
よって、最初の . と o の数の和から最大マッチ数を引いたものが答え。
例えば、最初の盤面が、
.xo..
x...x
o.o.o
x...x
.xox.
であった場合、ペアを作ると、
.xAA.
x.E.x
BBECC
x.D.x
.xDx.
以上のように A から E のペアが5つできてしまう。
よって、o を5つ囲うには x が5つ必要と判定できる。
したがって、この問題は一見最大フローの問題のように見えないが、
o と隣り合う . の２部マッチングの問題とみなすことができる。
３、最小カット
最小カットは損益を最小にして最大値を求めるアルゴリズムです。
ただし、実際に解く場合は最大流フローのアルゴリズムを用います。
最小カットは考え方であって、実際のコードは最大流フローです。
では、簡単な例を考えます。
問題
Aを選べば20点、Bを選べば10点です。
AかBのどちらかを選びます。
得られる最大の点数は何点か？
最大流フローはグラフなのでグラフを書いてみます。
よく考えずに直感で書いてみます。
ソース →(20)→ A →(∞)→ B →(10)→ シンク
AとBの順番はどちらでも構いません。
最大流だと10だけ流せることになるので、答えは10です。
しかし、答えは普通に考えて10ではありません。
よって、次のように考え方を変えます。
AとBを両方選べるのであれば合計30点もらえます。
よって、Aを選ぶと20だけ損をする。
Bを選ぶと10だけ損をする、と考えます。
グラフを書いてみます。
ソース →(20)→ A →(∞)→ B →(10)→ シンク
全く同じグラフです。
最大流は10だけ流せることになります。
これはBを選んだほうが損益が10で最小になると考えます。
よって、全体の利益30から最小の損益10を引いて30-10=20点が答えです。
この例は非常にバカバカしいように思えますが、
これがわからないとこの先どんどんわからなくなってくるので、
覚えておきましょう。
４、最小カットをちょっとややこしくしてみる
問題
Aを選べば20点、Bを選べば10点です。
また、Cを選べば30点、Dを選べば40点です。
AかBのどちらかを選びます。
CかDのどちらかを選びます。
得られる最大の点数は何点か？
これも損益のグラフにします。
→(20)→ A →(∞)→ B →(10)→
ソース シンク
→(30)→ C →(∞)→ D →(40)→
上のようなグラフで正しいです。
全体の利益は20+10+30+40=100です。
AとBを選ぶ場合の最小の損益は10です。
CとDを選ぶ場合の最小の損益は30です。
最小の損益は10+30で40です。
よって、すべての利益100から40を引いて100-40=60点が答え。
５、最小カットをややこしくしてみる
問題
Aを選べば20点、Bを選べば10点です。
また、Cを選べば30点、Dを選べば40点です。
AかBのどちらかを選びます。
AかDのどちらかを選びます。
CかDのどちらかを選びます。
得られる最大の点数は何点か？
前の問題はAとBが同時に選べないだけでしたが、
今回はAとDも同時に選べません。
→(20)→ A →(∞)→ B →(10)→
↓
ソース →(∞)→ シンク
↓
→(30)→ C →(∞)→ D →(40)→
以上のグラフを見てよく考えます。
すべて選べる場合の利益は20+10+30+40=100です。
この問題の場合AとBも同時に選べないので、
AからDに向かっても→(∞)→で繋いでいます。
このフローではどのように流れるでしょうか？
ソース→A→B→シンクで10だけ流れます。
ソース→A→D→シンクで10だけ流れます。
ソース→C→D→シンクで30だけ流れます。
よって、最小の損益は10+10+30=50ということになります。
よって最大の利益は100-50=50点ということになります。
ここで例えば、「AかCのどちらかを選びます。」
という条件の追加が可能かどうかを考えてみます。
これはできません。
いままでの問題はAとCが左のグループ、BとDが右のグループ
とみなして組み合わせを作ってきました。
AとCのグループ内で条件を作ることはできません。
どうしても条件を作りたいと考える時、
AもしくはCを他のグループに移動するという手もあります。
しかし、他のグループ内での整合性がとれなくなると失敗します。
６、ややこしい問題の応用（その１）
問題
Aを選べば20点、Bを選べば10点です。
また、Cを選べば30点、Dを選べば40点です。
AかBのどちらかを選びます。
CかDのどちらかを選びます。
Aを選んだら必ずCを選ぶ。
得られる最大の点数は何点か？
前の問題は「AかDのどちらかを選びます。」でしたが、
「Aを選んだら必ずCを選ぶ。」に変えました。
AとCで条件をつけることはできないと書いたばかりですが、
この条件の設定は可能です。
→(20)→ A →(∞)→ B →(10)→
↓ ↑
ソース →(∞)→ シンク
↑ ↓
→(30)→ C →(∞)→ D →(40)→
（注：中央でA→DとC→Bがクロスしています。）
以上のグラフを見てよく考えます。
すべて選べる場合の利益は20+10+30+40=100です。
CからBに向かっても→(∞)→で繋いでいます。
AとBは同時に選べません。
AとDも同時に選べません。
CとBも同時に選べません。
CとDも同時に選べません。
よって、AとCを同時に選ぶかBとDを同時に選ぶしかありません。
AとCで条件を作ることはできませんが、
結果的にAとCで条件を作れたとみなせます。
７、ややこしい問題の応用（その２）
問題
Aを選べば20点、Bを選べば10点です。
また、Cを選べば30点、Dを選べば40点です。
AかBのどちらかを選びます。
AとDの両方を選ぶと5点の減点です。
CかDのどちらかを選びます。
得られる最大の点数は何点か？
前の問題は「AかDのどちらかを選びます。」でしたが、
「AとDの両方を選ぶと5点の減点です。」に変えました。
→(20)→ A →(∞)→ B →(10)→
↓
ソース →(5)→ シンク
↓
→(30)→ C →(∞)→ D →(40)→
以上のグラフを見てよく考えます。
すべて選べる場合の利益は20+10+30+40=100です。
AからDに向かってのフローを→(5)→に変えました。
このフローではどのように流れるでしょうか？
ソース→A→B→シンクで10だけ流れます。
ソース→A→D→シンクで5だけ流れます。
ソース→C→D→シンクで30だけ流れます。
よって、最小の損益は10+5+30=45ということになります。
よって最大の利益は100-45=55点ということになります。
いままで使っていた∞の条件は減点が∞とい意味でした。
減点が∞のときはAとDを同時に選ぶことはできません。
この例では減点5点でも有利なのでAとDを同時に選びます。
このように減点を数値で指定することもできます。
また、「AとBの両方を選んでも良い。」であれば、
減点を0点にしてやれば良いこともわかります。
８、最小カットのもっとややこしい議論
以下のようなグラフを考えます。
→(20)→ A →(∞)→ B →(50)→
↑
ソース ←(∞)← シンク
↑
→(30)→ C →(∞)→ D →(10)→
このような接続に意味があるのか？が議論のテーマです。
いわゆる右のグループから左のグループに戻るフローです。
実際にこのフローを含むグラフをいくつか検証してみました。
右のグループから左のグループに戻るフローを書いてしまうと、
例えばAとBは同時に選べないといった整合性が崩れます。
よって、いまのところこのような接続はしてはいけないと考えます。
詳しく知っている方の見解を知りたいです。
９、このような例もある
以下の例で最大フローは4流れる。
→(100)→ A →(∞)→ B →(1)→
↓
→(∞)→
↓
ソース →(1)→ C →(∞)→ D →(1)→ソース
↓
→(∞)→
↓
→(1)→ E →(∞)→ F →(100)→
すべて選べる場合の利益は100+1+1+1+1+100=204だから、
最小の損益4を引いて204-4=200点になる。
よって、AとFを選べば最高点をとることができる。
CとDはどちらも選ぶことは無い。
3対3の選択でも答えは2個になりうることはある。
このような例も実際にはありえるので注意する。
１０、まとめ
最小の損益を求めて全体から引くことで最大の利益を求める。
選択が２群に分けることができるのが前提。
「一方しか選べない。」条件の指定が簡単。
群と他群間で「選べない。」もしくは「選ぶと減点。」の設定が可能。
応用すると同じ群内で「同じ選択をする。」という条件にできる。
１１、最小カットの応用
問題
Aを選ぶと20点もらえる。
Bを選ぶと10点もらえる。
Cを選ぶと15点の減点。
Dを選ぶと5点の減点。
Aを選んだらCを選ぶ。
Aを選んだらDを選ぶ。
Bを選んだらDを選ぶ。
→(20)→ A →(∞)→ C →(15)→
↓
ソース →(∞)→ シンク
↓
→(10)→ B →(∞)→ D →(5)→
得られる点数の最大は20+10=30点である。
最小カットのコストは20であるので、
得られる最大の点数は30-20=10点である。
加点と減点の２群のフローの作成が可能である。
１２、もっと簡単な最小カット
最小のコストを求めるのに最小カットが使えます。
問題
N個の町と町と町をつなぐM本の道があります。
スタートの町とゴールの町があります。
目的はスタートからゴールへたどり着けなくなるように、
町と道を壊すことです。
町を壊すとその町を経由できなくなります。
道を壊すとその道は通れなくなります。
町や道を壊すにはそれぞれコストがかかります。
スタートとゴールの町は壊すことができません。
最小のコストはいくらでしょうか？
この問題は最小コストを求める問題なので、
そのまま最小カットの問題と考えて問題ありません。
例えば次のような町と道の構成だとします。
スタート →道(20)→ 町(30) →道(10)→ ゴール
このようなグラフになったとします。
このとき最小カットで求める値は10になります。
よって、最小のコストは10で良いことになります。
もっと複雑な場合を考えるます。
すると上のグラフでは不適切であることがわかります。
町に対して道から入ってくる場合と出て行く場合の方向が、
グラフを作っている段階では不定だからです。
すべての道について町に入る用と町から出る用が必要です。
町についても入口と出口に相当するようなものを作る必要があります。
上の例は次のように書き換える必要があります。
→道(20)→ 町の入口 ←道(10)←
↓
スタート (30) ゴール
↓
←道(20)← 町の出口 →道(10)→
このようなグラフの作り方はよくあるので覚えておくと良い。
１３、最小費用流問題
最小費用流はそのまま最小の流量を求めるのに使うこともありますが、
最小カット問題と同じく最良の選択を行う組み合わせの選択に使うこともできます。
最小費用流はダイクストラのアルゴリズムとベルマンフォードのあるゴリズムがあります。
負のコストがあればベルマンフォードを使います。
負のコストが無ければ処理が速いのでダイクストラを使います。
最小費用流とは？
最小費用流ではエッジに流量とコストが決まっており、
与える流量を最小のコストで流すときのコストを求める。
例えば、以下の例
→(1,20)→ A →(∞,0)→ C →(1,15)→
↓
ソース(2) →(∞,5)→ シンク
↓
→(1,10)→ B →(∞,0)→ D →(1,5)→
ソースから流れる流量は2と決まっています。
括弧内の(r,c)はrが流量、cがコストを表します。
この場合2の流量を流そうと思うと、
ソース→A→C→シンク、ソース→B→D→シンクで1つずつ流す必要があります。
A→Dのルートが流れるとコストは低いですがすべての流量が流れません。
このときの総コストは(20+15)+(10+5)=50になります。
例えば、D→シンクを流量2、コスト5にします。
→(1,20)→ A →(∞,0)→ C →(1,15)→
↓
ソース(2) →(∞,5)→ シンク
↓
→(1,10)→ B →(∞,0)→ D →(2,5)→
これであれば、
ソース→A→D→シンク、ソース→B→D→シンクで2つの流したほうがコストが低くなる。
このとき総コストは(20+5+5)+(10+5)=45と低くなる。
与えた流量が流れないグラフの場合は-1を返します。
#define MAX_V 50
#define INF 1000000000
typedef pair<int, int> P;
struct edge{int to, cap, cost, rev;};
int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V];
int preve[MAX_V];
void ae(int from, int to, int cap, int cost){
G[from].push_back((edge){to, cap, cost, G[to].size()});
G[to].push_back((edge){from, 0, -cost, G[from].size() - 1});
}
int minCostFlow(int s, int t, int f){
int res = 0;
memset(h,0,sizeof(h));
while(f > 0){
priority_queue<P, vector<P>, greater<P> > que;
for(int i = 0; i < V; i++){
dist[i] = INF;
}
dist[s] = 0;
que.push(P(0,s));
while(!que.empty()){
P p = que.top(); que.pop();
int v = p.second;
if(dist[v] < p.first)continue;
for(int i = 0; i < G[v].size(); i++){
edge &e = G[v][i];
if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
que.push(P(dist[e.to], e.to));
}
}
}
if(dist[t] == INF){
return -1;
}
for(int v = 0; v < V; v++){
h[v] += dist[v];
}
int d = f;
for(int v = t; v != s; v = prevv[v]){
d = min(d, G[prevv[v]][preve[v]].cap);
}
f -= d;
res += d * h[t];
for(int v = t; v != s; v = prevv[v]){
edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return res;
}
int main(){
V = 6;
ae(0,1,1,20);
ae(0,2,1,10);
ae(1,3,INF,0);
ae(1,4,INF,5);
ae(2,4,INF,0);
ae(3,5,1,15);
ae(4,5,2,5);
cout << minCostFlow(0,5,2) << endl;
return 0;
}
１４、最小費用流の応用
最小費用流のアルゴリズムを組み合わせ選択の問題に使ってみます。
問題
AグループとBグループでペアになっている数字がある。
Aグループの数字はBグループの数字以下でなければならない。
Aグループ内の数字はコスト1で移動できる。
条件が整うようにAグループの数字を最小コストで入れ替えよ。
できない場合は-1を答えとせよ。
例えば、
(Aグループ、Bグループ)=(1,4),(2,1),(3,2),(3,3)
このとき(2,1)と(3,2)と(1,4)でAグループの数字を入れ替える。
するとコスト3で条件を満たすことができる。
このとき最小費用流でグラフを描いてみる。
まずBグループ基準でペアを昇順でソートする。
→(1,0)→ A2 →(1,1)→↓ A1 → B1 →(1,0)→
↓ ↓
→→↓ (∞,0)
↓ ↓
→(1,0)→ A3 →(1,1)→↓ →→→→ B2 →(1,0)→
↓ ↓
ソース(4) →→→↓ (∞,0) シンク
↓ ↓
→(1,0)→ A3 →→→→(1,0)→→→→ B3 →(1,0)→
↓
(∞,0)
↓
→(1,0)→ A1 →→→→(1,0)→→→→ B4 →(1,0)→
↓
(1,1) → B1
このように移動しない場合には流量1、コスト0のエッジを張る。
もちろん条件を満たさず移動しないといけない場合にはこのエッジは張れない。
移動する場合は数字を移動できる最小の数字にコスト1のエッジを張れば良い。
移動したらそれ以上の数字に移動できるように数字の大きいほうへ無限の流量、コスト0のエッジを張る。
流量は4で流さなければならないので最小のコストでペアを作って流すことになる。
このようにコストを最小にする組み合わせの選択の問題で最小費用流を使うことができる。
逆に、最小費用流で最小のロスを求めて利益を最大にするような問題も作れる。
