iriszero   9달 전

0번을 source, N+M+1번을 sink

사람은 1~N, 작업은 N+1~ N+M까지


capacity는

a. src와 사람은 2

b. 사람과 작업은 1

c. 작업과 sink는 1


로 해서 maximum flow 를 구했는데 accepted를 못 받았습니다.


어디가 잘못된 건지 알 수 있을까요?


https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp... 의 pseudo code 참고했습니다.

cubelover   9달 전

72줄과 73줄 사이에 graph[N+work].push_back(i); 를 추가해야 할 것 같습니다.

iriszero   9달 전

cubelover 죄송한데 이유를 좀 알 수 있을까요???

cubelover   9달 전

22줄에서 for (int v : graph[u]) 로 graph에 있는 간선들을 보고 있는데, graph에 사람->일 간선만 들어있고 일->사람 간선이 없어서 maximum flow가 구해지지 않을 수 있습니다.

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