5651번 - 완전 중요한 간선
최대 유량을 구한 뒤,
u->v인 각 간선을 돌면서
u->v로 유량을 흘러 보낼 수 있으면 Crucial Link가 아니고 흘러 보낼 수 없으면 Crucial Link라고 생각했는데
계속 틀렸습니다가 뜨네요. 맨 첨엔 DFS 구현을 잘못했나 싶어서 DFS 주석처리하고 아래 kkw564님 질문글과 비슷하게 BFS로 구현했는데 계속 50%에서 틀립니다.
Edge와 addEdge는 종만북 참고했습니다
며용
자문자답 갑니다.
왜냐하면 완전 중요한 간선을 찾을 때 원래 간선의 반대방향 간선도 고려했기 때문이었습니다!
그럼 이만 ~
그러면 중요한 간선을 찾는 반복문 내의 if문에
adj[here][k]->capacity != 0
조건도 추가해주면 되는 건가요??
@jaejin_me
넵 맞습니다
댓글을 작성하려면 로그인해야 합니다.
kinssang 6년 전 1
최대 유량을 구한 뒤,
u->v인 각 간선을 돌면서
u->v로 유량을 흘러 보낼 수 있으면 Crucial Link가 아니고 흘러 보낼 수 없으면 Crucial Link라고 생각했는데
계속 틀렸습니다가 뜨네요. 맨 첨엔 DFS 구현을 잘못했나 싶어서 DFS 주석처리하고 아래 kkw564님 질문글과 비슷하게 BFS로 구현했는데 계속 50%에서 틀립니다.
Edge와 addEdge는 종만북 참고했습니다