AtCoder Regular Contest 085 + AtCoder Beginner Contest 078

™ @tmaehara

最大流が枝変数（頂点流量制約）なのだから、双対の最小カットは当然頂点変数でしょー。

nico_shindannin（診断人） @nico_shindannin

@tmaehara 双対問題の部分は分かるのですが、 例のツイートの主張は、 「最小カットは、頂点変数pと辺変数dに対して最適化問題」であるのに、双対問題を理由にして「最小カットは、頂点変数p*のみ*に対しての最適化問題」と考えるのはおかしいというのが自分の主張でした。

™ @tmaehara

@nico_shindannin 頂点変数pが定まれば自動的に枝変数は決まるので、従属変数を簡約化するかどうか、という話ですかね。

nico_shindannin（診断人） @nico_shindannin

@Komaki__ ごめんなさい。恐らくkomakiさんがそう思ってると思ったので、巻き込まないようにしようと思ってました（例えば、新しい記事では、komakiさんの解法は書かず、問題の命名者も出しませんでした）。ただし、完全に避けるのは難しかったです…。

nico_shindannin（診断人） @nico_shindannin

@yosupot 聞いておいてすぐ返信できず、すいません。 自分の感想としては、この問題については、どの手法でも解けるなぁというかんじです。ただ、一般のその他の最小カット問題が出た場合、辺ベースで考えると、最初で詰まることがありそうで、その点は頂点ベースのほうがいいかなと思ってます。

nico_shindannin（診断人） @nico_shindannin

@yosupot 個人的には、よすぽさんにまた新しい最小カットの出題を期待してます（n択ベースっぽく見えるが、安易にそう考えると、すぐ詰む問題とか）。返信ありがとうございました！

Komaki @Komaki__

@nico_shindannin 気を使わせてしまったようですいません。燃やして埋めたいほどは恥ずかしくないので気にしないでください。100で言ったら2か3程度なので。

nico_shindannin（診断人） @nico_shindannin

太古の時代には、「電線をsからtに繋がらないようにする最小のコストを求めよ」とか、「答えは最小カットですよ」と言わんばかりの問題もありました。が、無くなりました。 教育的な最小カットの出題（安易なアプローチはすぐ詰む）に期待じゃ。もしくは、そういった問題のまとめ記事でも。

nico_shindannin（診断人） @nico_shindannin

マラソンマッチ勢の熱意を感じるランキングじゃ…

nico_shindannin（診断人） @nico_shindannin

@tmaehara [A]枝変数dを定める（自動的に頂点変数pが決まる） [B]頂点変数pを定める（自動的に枝変数dが決まる） で、ある種の最小カット問題を解くときに、[A][B]のどちらが考えやすいか？というのが話題の1つになってまして、「最大流の双対から考えると[B]」という意見への、返答というかんじでした。

nico_shindannin（診断人） @nico_shindannin

では、燃やす埋めるについてはこれぐらいにして、日立北大マラソンで、がんばります。

™ @tmaehara

@nico_shindannin 具体的な問題に対してどちらが考えやすいか、という話なら問題依存（∴両方できるべし）になりそうです。理論屋は (1) 頂点変数に取ると任意の部分集合が実行可能になる、(2) 頂点変数のほうが関数の性質が良い（枝から頂点を定められる条件が複雑）、という理由で頂点変数にとることが多いです。

™ @tmaehara

変分法だって関数空間上の一点を探してるだけなので、そこはしゃーない

ＳＫＹ/sky58🍊 @skyaozora

これは確かにそうで、自分も最小カットは「カットする辺を選ぶもの」と捉えてたけど、そうすると上手くいかない問題もあって、「最小カットは頂点をS/Tの2色に分ける分け方を選んで、切られる辺はそのあと自動的に決まる」と教えてもらったら上手く捉えられるようになった　twitter.com/yosupot/status…

よすぽ @yosupot

ARCに最小カットを出したら最小カットが結構話題になったっぽいんですが、最小カット問題を「辺を選ぶ」問題、つまり辺をいくつか選んでS, T間のパスを消す問題、と認識してしまうと、かなり(プロコンにおいては)損だと思います

2017-11-15 00:08:08

ＳＫＹ/sky58🍊 @skyaozora

てかこの日記で例として挙げられてるSRM653Div1Med、まさに自分が適当にグラフを組んだ結果元とは違う問題を解く最小カットになってしまって（AにもBにも属さないが問題では許されてないのに許してしまった）落としたやつだ･･･　yosupo.hatenablog.com/entry/2015/03/…

HIR180 @HIR180

codeforces.com/contest/704/pr… 最小流量制限ありフローが出されてるの(自分が出した以外で)初めて見た....

HIR180 @HIR180

@DEGwer3456 こどふぉとかSRMとかAtcoderあたりだとそんなに多くない気がします (OpenCupとかICPC系ならたくさんありそう)

ＳＫＹ/sky58🍊 @skyaozora

@HIR180 自分はこの問題で最小流量制限ありフローの解き方を習得しましたね

HIR180 @HIR180

@skyaozora なるほどです、蟻本にチラッと載ってるけどあんまり問題を見ないので珍しさがあります(？)

nico_shindannin（診断人） @nico_shindannin

@tmaehara なるほど、頂点変数をとるメリットが分かりました。丁寧な返信ありがとうございます m(_ _)m