search

NASU41 / AtCoderLibraryForJava

Creative Commons Zero v1.0 Universal
78 stars 23 forks source link

2-SAT #17

Open m1zz1y opened 4 years ago

m1kit commented 4 years ago

https://github.com/m1kit/competitive-lib/blob/master/src/dev/mikit/atcoder/lib/misc/TwoSat.java

suisen-cp commented 4 years ago

とりあえず SCC に依存しないように 2 SAT の中に SCC を貼っています.

SCC は細かい高速化を入れているので結構速くなっていると思います.

NASU41 commented 4 years ago

「変数xの値がfに確定した」とか書きたくなりませんかね addClause(x,f,x,f)とすればいいのですが, 頻出なら関数化したくなるもので

suisen-cp commented 4 years ago

確かにあるとよいかもしれません．関数名をどうしましょうか

NASU41 commented 3 years ago

とりあえず set(int x, boolean f) でコード書きました.