각 쥐에서 각 구멍까지 갈 수 있는지 여부를 쥐-구멍 직선경로가 어떠한 벽과 교차하는지(끝만 건드리는 케이스는 무시하고) 판단한 후, source에서 쥐까지 용량 1 에지, 쥐에서 갈 수 있는 구멍까지 용량 1 에지, 구멍에서 sink까지 용량 K 에지를 만들어 최종 플로우가 쥐의 갯수와 일치하는지를 판단하는 것까지는 잘 판단해냈는데 코드가 틀렸네요..
Dinic은 여기서 끌고 온 코드고, intersect함수는 첫번째 선을 (벡터 형식으로) A+ta, 두 번째 선을 B+sb로 두고, 구체적인 교차 여부를 반환하고 만약 교차점이 존재한다면 교차점에서의 t,s를 기록해두는 함수인데, 이 함수는 다른 문제에서 테스트를 해 보아, 기하+플로우 두 부분 코드 모두 어느 정도 정확하다고 생각하고 있었는데 4%에서 바로 틀려버리네요.. 어디서 잘못된 것일까요??
dlwocks31 5년 전
소스 코드: http://boj.kr/496658765afb4b0e...
각 쥐에서 각 구멍까지 갈 수 있는지 여부를 쥐-구멍 직선경로가 어떠한 벽과 교차하는지(끝만 건드리는 케이스는 무시하고) 판단한 후, source에서 쥐까지 용량 1 에지, 쥐에서 갈 수 있는 구멍까지 용량 1 에지, 구멍에서 sink까지 용량 K 에지를 만들어 최종 플로우가 쥐의 갯수와 일치하는지를 판단하는 것까지는 잘 판단해냈는데 코드가 틀렸네요..
Dinic은 여기서 끌고 온 코드고, intersect함수는 첫번째 선을 (벡터 형식으로) A+ta, 두 번째 선을 B+sb로 두고, 구체적인 교차 여부를 반환하고 만약 교차점이 존재한다면 교차점에서의 t,s를 기록해두는 함수인데, 이 함수는 다른 문제에서 테스트를 해 보아, 기하+플로우 두 부분 코드 모두 어느 정도 정확하다고 생각하고 있었는데 4%에서 바로 틀려버리네요.. 어디서 잘못된 것일까요??