WUPC2019F
考えたこと
最小カットに帰着することは既知
「疲労」と「元気」の2つの状態があるから素直にカットになる
グラフの頂点を通過すると状態が変わる
つまり頂点の「通過前」と「通過後」の状態がある
元気状態で開始なので元気がS
クリア時の状態はどちらでもいいことをどう表現するか？
ここまでの考察を図にまとめる
戦闘場面では手前が元気で、後が疲労である
回復可能場面では疲労から回復になることができて、コストを支払う
グラフの形状について「閉路はない」条件
閉路はないが合流はあるよな？
入力例1に合流がある
違う状態で合流した時どうなるのか？
「上流のいずれかが元気Sならその頂点も元気S」
「上流のすべてが疲労Tの時のみ疲労T」
「いずれかがSならSである」は無限大辺を張るだけで良い
しかしそれだけではすべてTのときにSにもTにもなれる
あ、わかった、問題制約の勘違いだ
ユーザがどのような道を通っても、戦闘までに回復ポイントを通る、という制約
つまり2通りの道があって、その中のいずれかがTなら合流後もT
全部SならSにもTにもなれるが、Tになってもコストが増えるだけなので問題ない
(ここ、もうちょっとハッキリした言い方をしたい)
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]