WUPC2019F

https://gyazo.com/b7d9e87ab5927f6a16affa0feaadd2e2

考えたこと

最小カットに帰着することは既知

「疲労」と「元気」の2つの状態があるから素直にカットになる

グラフの頂点を通過すると状態が変わる

つまり頂点の「通過前」と「通過後」の状態がある

元気状態で開始なので元気がS

クリア時の状態はどちらでもいいことをどう表現するか？

ここまでの考察を図にまとめる

戦闘場面では手前が元気で、後が疲労である

回復可能場面では疲労から回復になることができて、コストを支払う

https://gyazo.com/ffa8cbd1d6ea78c3997491877cb77fb4

グラフの形状について「閉路はない」条件

閉路はないが合流はあるよな？

入力例1に合流がある

違う状態で合流した時どうなるのか？

「上流のいずれかが元気Sならその頂点も元気S」

「上流のすべてが疲労Tの時のみ疲労T」

「いずれかがSならSである」は無限大辺を張るだけで良い

しかしそれだけではすべてTのときにSにもTにもなれる

https://gyazo.com/04ed2dd16f5371ca5aca65cf11312711

あ、わかった、問題制約の勘違いだ

ユーザがどのような道を通っても、戦闘までに回復ポイントを通る、という制約

つまり2通りの道があって、その中のいずれかがTなら合流後もT

全部SならSにもTにもなれるが、Tになってもコストが増えるだけなので問題ない

(ここ、もうちょっとハッキリした言い方をしたい)