SRM 594

agw @masashinakata

おかげで、なんてこった@simezi_tanさんのエントリ読むの忘れてたことに気付いた（・∀・）: TopCoder SRM 594 Div1 Medium FoxAndGo3 - simezi_tanの日記: http://t.co/OwqoIBaTCP

nico_shindannin（診断人） @nico_shindannin

Wikipediaに載ってる最小カットの式、これであってるのかなぁ…。 http://t.co/uilkPcYTzG

nico_shindannin（診断人） @nico_shindannin

カットして、sが含まれる集合に属する頂点xをPx=1、t側の頂点はPx=0とすると、カットする辺Dij=1、カットしない辺Dij=0のとき最小値をとりそうで合ってそうと最初は思ったんだけど、整数の制約がないので小数を許せばΣCijDijiの値をもっと小さくできるように見える…

nico_shindannin（診断人） @nico_shindannin

最大フロー→最小カットの双対のやつ、機械的に変形すれば、まぁで納得できるだろうと勝手に思ったのですが、微妙に合わない…

agw @masashinakata

s-tカットのいいページ発見（・∀・）: 蟻本P191 最大流 - 最小カット定理 - WARush: http://t.co/tnBjJFRS9c

nico_shindannin（診断人） @nico_shindannin

わかった。wikipediaのやつはあってる。Min-cutでPが小数をとるのはOKだ。ただ、一部の例外を除いて、Pが小数のとき最小値をとるのはありえなさそう。

nico_shindannin（診断人） @nico_shindannin

たぶん、流れる辺のコストが同じとき、pが小数で

nico_shindannin（診断人） @nico_shindannin

最小値になることはありえるけど、そういう場合は、pが1,0でも必ず最小値のケースがあるはず

nico_shindannin（診断人） @nico_shindannin

0,1のとき最小値をとりうるというのは、そのままだと証明するのが難しいので、パス基準の式におきかえてから双対をとってると理解。これみたいに→ http://t.co/gsAUl5AekW

nico_shindannin（診断人） @nico_shindannin

まぁ、グラフの専門家じゃないから、これぐらいの理解でいいや

nico_shindannin（診断人） @nico_shindannin

これでやっと、もやもや感なしにMax-flow min-cutがつかえるｗ

けんちょん @drken1215

SRM558 DIV1 Hard、ガチで感動！ これの思いつき方だけど………多分、（ちょっとうまく言えないけど…）「アカン関係にある2人」の構造が2部グラフになっていれば、結局最小カットに持ち込めて、2部グラフになっていなければ、結局最小カットにはできない、的な感じかな。

けんちょん @drken1215

「アカン関係」は左右フリップすればいい。アカン関係が2部グラフじゃなかったら、どうフリップしても詰む。2部グラフならうまくフリップして、全部OKな関係になる。

けんちょん @drken1215

全然説明になってない………

けんちょん @drken1215

最小カットを極める

Ryo Sugihara @sugiryo

@nico_shindannin "total unimodularity"で調べてみてください。

nico_shindannin（診断人） @nico_shindannin

@sugiryo 情報ありがとうございます！全然知りませんでした。問題によっては、最適解がとりうるのは、小数になってしまうのもありうるんですね。

nico_shindannin（診断人） @nico_shindannin

@drken1215 drkenさんのツイートみて、答えみてみたら、これ超難しいです。最小カットは甘くなかった…。

Ryo Sugihara @sugiryo

@nico_shindannin LPのfeasible regionのpolyhedraのvertexが全て整数になるので、simplexで解く限り最適解は常に整数になるという理解です。もちろん最初に書かれてたように、同じ最適値で解が複数（無限）にある場合は小数の解も含みます。

nico_shindannin（診断人） @nico_shindannin

@sugiryo なるほど、分かりやすいです。線形計画法では、条件をみたす領域の多角形の頂点のうち必ず１つは解になるので、頂点の座標が常に整数なら、いつでも整数解があるということですね。

nico_shindannin（診断人） @nico_shindannin

最小カットのProject selection problem系問題の難易度順：Komakiさんの燃やす埋める問題＝Dual Core CPU（蟻本にある）＜SRM594 Div1Med＜The Year of Code Jam（蟻本最終問題）＜＜SRM558 Div1Hard

nico_shindannin（診断人） @nico_shindannin

The Year of Code JamとSRM558 Div1Hardの中間の難易度の問題ないかなぁ。

komiya @kou_miyam

@nico_shindannin 自分で作った問題の宣伝＆その2題とネタ被り（パクリ？）ですがAOJ2496解いてもらえると私が喜びます

nico_shindannin（診断人） @nico_shindannin

@kou_miyam おお、ありがとうございます。こういう情報助かります。早速やってみますね。

けんちょん @drken1215

@nico_shindannin いやー、ホントに、「こんな世界もあるんだ！！！すげぇえええええええええ！！！！！！」と感動しました！！！！！！！！