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