index   4년 전

제 경우에는 역간선에 유량을 잘못 흘려줘서 틀렸던 거였어요.

에드몬드-카프나 디닉을 쓰는 경우 우선 1->4->3->2로 먼저 유량이 흐르는데 이를 다시 1->5->6->7->3->2와 1->4->8->9->10->11->(14->)15->16->17->2로 제대로 나눌 수 있는 지 확인해야 해요.

또 정점 처리를 잘못 하는 경우에도 이런 문제가 생길 수 있어요

iktk   3년 전

저도 같은 유형으로 틀렸네요.

정점을 in과 out으로 분할했으니 A->B 링크에 대해 Ain->Bout, Bin->Aout 가 서로 역간선이라고 생각해버렸네요.

Bout->Ain, Aout->Bin도 빼먹지 말고 인접 리스트에 추가해야겠습니다.

jinik9903   3년 전

위 두 분 감사합니다!! 덕분에 삽질을 멈출 수 있었네요 ㅜㅜ

나중에 이 글을 보실 분들을 위해 조금 더 작은 반례 남깁니다!

8 9
1 3
3 4
4 2
2 6
6 5
5 3
1 7
7 8
8 4

preview

calculus   2년 전

정말 감사합니다!

Edmonds-Karp Algorithm 증명없이 써왔는데

덕분에 이를 역방향 flow가 있는 경우에 대해 좀 더 자세히 생각해볼 수 있는 좋은 기회가 되었습니다.

powerlsj7   2년 전

위의 그림 나온 예제로 테스트하다가 양쪽 간선 문제를 해결하였습니다. 감사드립니다!

jjiho0707   1년 전

인접리스트로 구현했는데 역간선을 추가 안한것이 문제였네요. 덕분에 해결하고갑니다. 감사합니다!

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