問題を解決する_最大フローを使用する

Question

私はこれを解決しようとしていますProblem。

偉大Charzehはジョフリーbaratheonがでゲームをプレイしているが、以下のように

問題文です。 7つの王国にはn人の騎士がいる。 i-th騎士の強さはai (0 ≤ ai < m)になります。黒い城の壁にはn+m-1 numbers f0, f1, ..., fn+m-2もあります。

「ゲーム」は2ターンで構成されています。最初のターンで、Charzehは数字0, 1, ..., n-1 like p0, p1, ..., pn-1の順列を選択します。

第2ターンでは、Joffreyは、i (0 ≤ i < n)を選択してから、Winterfellのランダムな住民fpi + aiを受け入れます。チャゼは親切で、ジョフリーは残酷です。だから、チャーゼは最小化しようとしており、ジョフリーは斬首人を最大限にしようとしている。

両方が最適に再生される場合、死ぬ人は何人ですか？入力用

：私はそれは最大分UMフローを使用して解決することができる表示され論説を通じてつもりだとき

7 0 9 1 
5 61 53 6 7 72 75 42 5 79 91 5 16 

回答は7

です。私はこのアルゴリズムがどのようにここで働くかを知らない。誰でも私にこれを解決する方法を教えてもらえますか？すなわち、このアルゴリズムがここでどのように働くかを私に知らせてください。

Answer 1

唯一の重要な値はmax(fpi + ai)です。だから質問は実際には、最小値がXであり、iのすべての値に対して少なくともfpi + ai <= Xの置換があるようなものです。

このような置換が存在するかどうかを確認するには、2部グラフを作成します。一方の側にはfの位置に対応するノードがあり、他方にはaの値に対応するノードがあります。 f[x]とa[y]の間にエッジがあります。f[x] + a[y] <= Xの場合、すなわち、f[x]とa[y]をペアにした置換がソリューションに適している場合です。すべてのウェイトは1にする必要があります。グラフの最大フローを計算できるようになりました。 n個のフロー単位を押すことができれば（n個のノードをすべて接続する）、これは初期条件（fpi + ai <= X）を満たす置換です。

これで、少なくともXのバイナリ検索が実行され、対応するグラフのn個の単位のフローをまだ見つけることができます。私が間違っていない場合は、複雑さはO(log(N+M)*N^3)、ログはバイナリ検索から、N^3はフローアルゴリズムからです。

Xを増やすと、対応するグラフは厳密に元のグラフのスーパーセット（Xを増やしてエッジを削除しない）を使用することもできます。これは、Xの値が小さいほど、これまでに見つかった部分解は、Xの値を大きくするためのフローを計算するための合理的な出発点であることを意味します。他の方法でも動作しますが、はるかに面倒です（エッジ条件を満たしておらず、グラフ内の別の接続を見つける）。しかし、パフォーマンスの最後のビットを絞る必要がない限り、私は余分な複雑さを気にしません。