AtCoderで一発逆転を狙う｜浅野学園物理部

はじめに

中3のkino0402です。競技プログラミングをやっています。去年の部誌ではAtCoderでの入水記事を書いたのですが…未だに水色から上がれていません。色変記事を部誌として書くことによって部誌作成を楽にする作戦が崩れてしまいました。このままでは部誌を書くことができないので、今週末のABCで一発逆転しての入青を狙うしかありません。

ところで皆さん、フローというアルゴリズムを知っていますか？フローというのは、理解が（比較的）難しくなく、（とあるものを使えば）実装量が少ないにも関わらず、AtCoderで出題された際には基本的に暖色diffになるという、知っていれば一発逆転を狙うことができるアルゴリズムです。 ABCでは、基本的にG問題に配置されているのですが、ABCでの1問の価値は非常に高く、難易度次第ではありますがG問題を解けるとperfが大きく上がります。早さ次第ではカンストperfも狙えるかもしれません。

ということで今回は、フローについて解説していきます。

フローとは何か

E - 最大流
https://atcoder.jp/contests/pastbook2022/tasks/pastbook2022_e

\(V\) 個の街があります。各街には \(1, 2, \cdots, V\) と番号が付いています。 \(E\) 本の水道管があり、 \(i\) 本目の水道管は街 \(u_i\) から街 \(v_i\) へ水を最大で \(c_i\) だけ流すことが出来ます。街1から街 \(V\) へ流せる水の量の最大値を求めてください。

このような問題を解くことができるアルゴリズムです。

フローの実装方法

Ford-Fulkerson法と呼ばれる方法で最大フローを求めていきます。このアルゴリズムでは、入力の通りに作ったフローグラフではなく、残り容量を順方向、使用済み容量を逆方向の辺として追加したグラフである、残余グラフを使います。以下の手順で最大フローを求めることができます。

残余グラフ上の、頂点 \(1\) から頂点 \(N\) までのパスを見つける。
そのパス上に流せるだけ流す。厳密には、パスにおける容量の最小値 \(F\) を求め、パス上に流量 \(F\) を流す。この時、逆方向の辺の流量を \(F\) 減らす。
パスが見つからなくなるまで、以上の動作を繰り返す。

なお計算量は、辺の数を \(E\) 、最大フローを \(F\) とした時、 \(O(EF)\) になります。

実装例はこちらになります。量が多く、100行ほどになってしまったので、こちらのリンクからご覧ください。

Submission #69228808 - 典型アルゴリズム問題集上級〜エキスパート編 https://atcoder.jp/contests/pastbook2022/submissions/69228808

これで最大フローが求められることの証明ですが、筆者が言語化できるほど理解していない、執筆時刻が部誌の締切前日の夜12時である、証明を書くには余白が狭すぎるなどの理由で載せることができません。申し訳ございません。

なお、AtCoderで問題を解くだけであれば、ほとんどの問題では必ずしも証明を理解する必要はありません。（もちろん理解するに越したことはないですが）なんなら、ACLという物を使えば、実装の理解ができなくてもある程度は解くことができます。

AtCoderにはACL(AtCoder Library)と呼ばれる、AtCoderが提供する、C++用アルゴリズム・データ構造ライブラリがあります。 ACLの使い方はここでは省略します（https://atcoder.github.io/ac-library/master/document_ja/maxflow.htmlを見てください）が、ACLを使うことで関数部分を省略し、このように短く書くことができます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;

int main() {
  ll V, A;
  cin >> V >> A;

  atcoder::mf_graph<ll> G(V);

  for (int i = 0; i < A; i++) {
    ll u, v, c;
    cin >> u >> v >> c;
    G.add_edge(u - 1, v - 1, c);
  }

  cout << G.flow(0, V - 1) << endl;
}

また、以下のような最小費用流問題というものもあります。

\(V\) 個の街があります。各街には \(1, 2, \cdots, V\) と番号が付いています。 \(E\) 本の水道管があり、 \(i\) 本目の水道管は街 \(u_i\) から街 \(v_i\) へ水を最大で \(c_i\) だけ流すことができますが、水を \(1\) 流すごとに費用が \(d_i\) かかります。街 \(1\) から街 \(V\) へ水を \(F\) だけ流すとき、合計費用の最小値を求めてください。

時間とページ数に余裕がないので実装方法などは省略しますが、これもACLを使うことで短く書くことができます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;

int main() {
  ll V, E, F;
  cin >> V >> E >> F;

  atcoder::mcf_graph<ll,ll> G(V);

  for (int i = 0; i < E; i++) {
    ll u, v, c, d;
    cin >> u >> v >> c >> d;
    G.add_edge(u - 1, v - 1, c, d);
  }

  cout << G.flow(0, V - 1, F).second << endl;
}

フローを使う問題

最小カット問題

辺ごとに決められたコストを払うことでその辺を消せる時に、頂点 \(1\) から頂点 \(N\) まで辿り着けないようにするためのコストを最小化する問題です。コストを辺の最大容量とすると、 \(1\) から \(N\) にフローを流した時の流量が答えになることが知られています。

ABC010-D 浮気予防（diff:1777）

最小カットの基本問題。
https://atcoder.jp/contests/abc010/tasks/abc010_4

ABC239-G Builder Takahashi（diff:2215）

消す物が辺ではなく頂点になっている。
https://atcoder.jp/contests/abc239/tasks/abc239_g

二部マッチング問題

\(N\) 組の点があり、ペアになれる二組の組み合わせがわかっているとき、ペアの個数を最大化する問題です。点 \(A1-A6\) , \(B1-B6\) のマッチングを考えます。頂点 \(S, G\) を作り、 \(S\) から \(A1-A6\) 、 \(G\) から \(B1-B6\) 、ペアになれる組み合わせに最大容量が \(1\) の辺を追加した時に、 \(S\) から \(G\) へ流せる量が答えになります。この場合は \(4\) です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
graph TD;
    S-->A1;
    S-->A2;
    S-->A3;
    S-->A4;
    S-->A5;
    S-->A6;
    B1-->G;
    B2-->G;
    B3-->G;
    B4-->G;
    B5-->G;
    B6-->G;
    A1-->B1;
    A4-->B3;
    A4-->B4;
    A4-->B5;
    A5-->B6;
    A2-->B2;
    A3-->B2;
    A6-->B6;

ABC091-C Plane 2N Points（diff:1268）

二部マッチングの基本問題。他の解き方もできる。
https://atcoder.jp/contests/abc091/tasks/arc092_a

典型90問-077 Planes on a 2D Plane（★7）

復元が必要。
https://atcoder.jp/contests/typical90/tasks/typical90_by

ABC401-G Push Simultaneously（diff:2022）

二部マッチング＋何か。
https://atcoder.jp/contests/abc401/tasks/abc401_g

燃やす埋める問題

この名前の由来になった問題を紹介します。

いくつかのゴミがあり、燃やすか埋めるかで全て処理する。 i個目のゴミは燃やすと \(a_i\) 円、埋めると \(b_i\) 円かかる。いくつかの「 \(x_i\) 個目のゴミを燃やし、 \(y_i\) 個目のゴミを埋めると \(z_i\) 円の罰金。」といった指示が与えられる。この時、かかる金額を最小化せよ。

頂点 \(S, G\) を作り、頂点 \(S\) から \(i\) に最大容量 \(a_i\) の辺を、頂点 \(i\) から \(G\) に最大容量\(b_i\)の辺を、頂点 \(x_i\) から \(y_i\) に最大容量 \(z_i\) の辺を追加した時、最小カット、つまり \(S\) から \(G\) まで流せる量が答えになります。

「両方埋める場合に罰金」、「燃やしたら \(a_i\) 円の報酬」、「全て燃やしたら報酬」など様々な応用パターンがありますが、ここでは解説しきれないので最小カットについて - よすぽの日記
https://yosupo.hatenablog.com/entry/2015/03/31/134336をご覧ください。

ARC085-E MUL（diff:2571）

燃やす埋めるの基本問題。
https://atcoder.jp/contests/arc085/tasks/arc085_c

ABC225-G X（diff:2566）

燃やす埋めるで解けると知っていると解きやすい問題。
https://atcoder.jp/contests/abc225/tasks/abc225_g

ABC326-G Unlock Achievement（diff:2470）

燃やす埋めるで解けると知っていると解きやすい問題2。
https://atcoder.jp/contests/abc326/tasks/abc326_g

最後に

ここまで長々書いてきましたが、なんと悲しいことに、8/30のABC421にてフローを使う問題が出題されたにも関わらず解けませんでした。なのでおそらく打越祭までに入青することはできないでしょう…これでは部誌を書くことができません。学校の友達にも「何があっても部誌を書く」ことは約束していますし。精神も壊れ、人間関係も壊れ、そして信用も失い、最終的には退学に追い込まれるかもしれません。

…あれ？部誌を書くための方法について考えていたら部誌と言えるレベルの内容が完成してしまいました。今年はこれで許されましたが、来年こそはちゃんと入青記事が書けるようにしたいですね。最後までご覧いただきありがとうございました。