appa   2년 전

입력으로 "u | v"가 주어진다면, !u → v 랑 !v → u 로 그래프를 만든 후에 SCC를 돌렸습니다.

1) 구한 SCC 집합들 중에서 p와 !p가 같이 있다.

2) 어떤 명제를 따라가다보니 p와 !p가 같이 있다.

두 가지를 고려해주니까 맞던데요.

1)만 고려하면 왜 틀린걸까요?

소스 첨부합니다~(p인 명제들은 1~n, !p인 명제들은 n+1~2n입니다.)

appa   2년 전

제 소스를 icpc live archive에 제출하면 WA가 나오는데 이유를 잘 모르겠네요;;;

pichulia   2년 전

저 go가 왜 있나 했더니

상근이는 심사위원의 의심을 받지 않으면서, 다음 라운드에 진출하는 목록을 만들 수 있는지를 알고 싶어 한다. 당연히 이 목록에는 상근이가 포함되어 있어야 한다.

문제에 저런 조건이 있어서 그랬군요....

2-sat을 돌렸는데 결과물이 상근이가 항상 false가 되도록 나온다면 안되겠죠ㅋㅋㅋㅋ

바꿔말하면, 1번 노드가 항상 true여야 하는데 이럴 경우 2-sat graph에 모순이 생긴다면, 제 아무리 2-sat의 해가 존재한다고 해도 상근이가 떨어지니까 의미가 없다는 것입니다... 뭐 이런 데이터로는 뭐가 있을까 고민되기는 하는데;; 

일단 랜덤 돌려서 나온 데이터는 아래와 같습니당;

댓글을 작성하려면 로그인해야 합니다.