2316번 - 도시 왕복하기 2
제 경우에는 역간선에 유량을 잘못 흘려줘서 틀렸던 거였어요.
에드몬드-카프나 디닉을 쓰는 경우 우선 1->4->3->2로 먼저 유량이 흐르는데 이를 다시 1->5->6->7->3->2와 1->4->8->9->10->11->(14->)15->16->17->2로 제대로 나눌 수 있는 지 확인해야 해요.
또 정점 처리를 잘못 하는 경우에도 이런 문제가 생길 수 있어요
저도 같은 유형으로 틀렸네요.
정점을 in과 out으로 분할했으니 A->B 링크에 대해 Ain->Bout, Bin->Aout 가 서로 역간선이라고 생각해버렸네요.
Bout->Ain, Aout->Bin도 빼먹지 말고 인접 리스트에 추가해야겠습니다.
위 두 분 감사합니다!! 덕분에 삽질을 멈출 수 있었네요 ㅜㅜ
나중에 이 글을 보실 분들을 위해 조금 더 작은 반례 남깁니다!8 91 33 44 22 66 55 31 77 88 4
정말 감사합니다!
Edmonds-Karp Algorithm 증명없이 써왔는데
덕분에 이를 역방향 flow가 있는 경우에 대해 좀 더 자세히 생각해볼 수 있는 좋은 기회가 되었습니다.
위의 그림 나온 예제로 테스트하다가 양쪽 간선 문제를 해결하였습니다. 감사드립니다!
인접리스트로 구현했는데 역간선을 추가 안한것이 문제였네요. 덕분에 해결하고갑니다. 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
index 4년 전 22
제 경우에는 역간선에 유량을 잘못 흘려줘서 틀렸던 거였어요.
에드몬드-카프나 디닉을 쓰는 경우 우선 1->4->3->2로 먼저 유량이 흐르는데 이를 다시 1->5->6->7->3->2와 1->4->8->9->10->11->(14->)15->16->17->2로 제대로 나눌 수 있는 지 확인해야 해요.
또 정점 처리를 잘못 하는 경우에도 이런 문제가 생길 수 있어요