kinssang   6년 전

최대 유량을 구한 뒤,

u->v인 각 간선을 돌면서

u->v로 유량을 흘러 보낼 수 있으면 Crucial Link가 아니고 흘러 보낼 수 없으면 Crucial Link라고 생각했는데


계속 틀렸습니다가 뜨네요. 맨 첨엔 DFS 구현을 잘못했나 싶어서 DFS 주석처리하고 아래 kkw564님 질문글과 비슷하게 BFS로 구현했는데 계속 50%에서 틀립니다.

Edge와 addEdge는 종만북 참고했습니다

kinssang   6년 전

며용


자문자답 갑니다.

왜냐하면 완전 중요한 간선을 찾을 때 원래 간선의 반대방향 간선도 고려했기 때문이었습니다!


그럼 이만 ~

jaejin_me   6년 전

그러면 중요한 간선을 찾는 반복문 내의 if문에

adj[here][k]->capacity != 0

조건도 추가해주면 되는 건가요??

kinssang   6년 전

@jaejin_me

넵 맞습니다

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