http://agc017.contest.atcoder.jp/tasks/agc017_e
解法1 解説放送・想定解
UF解 : http://agc017.contest.atcoder.jp/submissions/1414406
dfs解 : http://agc017.contest.atcoder.jp/submissions/1414474
解説放送の副読本的解法です。
手順は、
1. 解説放送の冒頭にあるように辺を作る (make_edge)
2. 入出次数を見て、矛盾が無いかチェック (in/out check)
3. 不当なサイクルが無いかをチェック (cycle check)
1.は解説放送にあるように場合分けをして辺を作る。
2.も解説放送にあるように入次数と出次数をそれぞれカウントし、頂点の正負によって場合分けして判定する
問題が、解説放送で省略されていた3.のやり方なのだが、他のプロの解答を見てると2通りあるので、2通り紹介する。
Union Findで判定
まずUnionFindで連結成分をまとめておく。
パスの始点になる所を考えて見ると、「正の頂点で出<入次数」の頂点である。
パスの終点になる所を考えて見ると、「負の頂点で入<出次数」の頂点である。
このパスと適当な頂点(500番)とをuniteする。
これで全ての使われている頂点とこの適当な頂点が連結かを判定し、1つでも非連結なものがあれば"NO"と返す。
こうやることで、ある連結成分において、パスの始点・終点の候補が1つもないものをあぶり出すことができる。
dfsで判定
パスの始点になる所を考えて見ると「正の頂点で出<入次数」の頂点であり、そこからdfsをして全ての頂点に到達可能かを判定する。
もし、判定不可能であれば、サイクルのみの部分だけ到達不可能となる。
解法2 最大流問題として解く
http://agc017.contest.atcoder.jp/submissions/1411763
http://agc017.contest.atcoder.jp/submissions/1411389
最小費用流として解けそうだと最初思ったけど、最大流なのか…よく分からない
