2311번 - 왕복 여행
http://boj.kr/510121e21b904567...
정답을 받은 제 소스는 위와 같습니다. 흔한 정점분할한 mcmf(+spfa) 소스입니다.
제가 궁금한점은 문제의 입력에서 A와 B가 반대로 주어져도 같은 결과를 내야 한다고 생각하는데 제 정답소스는 그렇게 동작하지 않습니다.
5 51 2 12 3 13 5 11 4 14 5 1
5 51 2 13 2 13 5 11 4 14 5 1
위의 소스에서는 2 3 1 과 3 2 1 이 A와 B가 반대로 주어져 있습니다.
제 소스는 위의 입력에 대해 5라는 기댓값과 같은 결과를 내고
아래 입력에 대해서는 2라는 잘못된 결과를 내고 있습니다.
i번 나라와 j번 나라가 도로로 연결되어 있으면 i번 나라에서 j번 나라로 이동할 수 있고, j번 나라에서 i번 나라로도 이동할 수 있다.
라는 문제의 조건이 있으므로 위 아래 입력이 같은 입력을 나타내고 있으며, 문제의 입력조건에 위배되지 않는다고 생각합니다만 제 소스가 왜 같은 입력이라고 생각하는 것에 상반된 결과를 내면서도 정답이라고 처리가 되는지 궁금합니다.
제가 위배되지 않는 부분 혹은 같은 그래프다 라고 생각하는 부분에 잘못된 부분이 있는지,
보유 테스트 케이스에선 단순히 이런 간선만 반대로 주는 입력이 없는지 궁금합니다.
댓글을 작성하려면 로그인해야 합니다.
tor012 5년 전 1
http://boj.kr/510121e21b904567...
정답을 받은 제 소스는 위와 같습니다. 흔한 정점분할한 mcmf(+spfa) 소스입니다.
제가 궁금한점은 문제의 입력에서 A와 B가 반대로 주어져도 같은 결과를 내야 한다고 생각하는데 제 정답소스는 그렇게 동작하지 않습니다.
5 5
1 2 1
2 3 1
3 5 1
1 4 1
4 5 1
5 5
1 2 1
3 2 1
3 5 1
1 4 1
4 5 1
위의 소스에서는 2 3 1 과 3 2 1 이 A와 B가 반대로 주어져 있습니다.
제 소스는 위의 입력에 대해 5라는 기댓값과 같은 결과를 내고
아래 입력에 대해서는 2라는 잘못된 결과를 내고 있습니다.
i번 나라와 j번 나라가 도로로 연결되어 있으면 i번 나라에서 j번 나라로 이동할 수 있고, j번 나라에서 i번 나라로도 이동할 수 있다.
라는 문제의 조건이 있으므로 위 아래 입력이 같은 입력을 나타내고 있으며, 문제의 입력조건에 위배되지 않는다고 생각합니다만 제 소스가 왜 같은 입력이라고 생각하는 것에 상반된 결과를 내면서도 정답이라고 처리가 되는지 궁금합니다.
제가 위배되지 않는 부분 혹은 같은 그래프다 라고 생각하는 부분에 잘못된 부분이 있는지,
보유 테스트 케이스에선 단순히 이런 간선만 반대로 주는 입력이 없는지 궁금합니다.