BUS문제는 Edmonds-Karp로 안되네요?ㅠㅠ

  • restart
    restart

    BUS문제

    굉장한 Editorial을 읽고.. Min cut을 찾기 위해
    s-t그래프를 구성하고 Edmonds-Karp를 돌렸는데 TLEㅠㅠ
    코드를 뚫어져라 쳐다봐도 잘못된 점은 잘 안보이고
    시간복잡도를 생각해보니 O(E²V)라 왜그런지 알 수 있었는데..

    그럼 좀 더 빠른 min cut알고리즘을 써야 한다는건데,
    Edmonds-Karp도 머리가 터질 것 같았던 저는.. 어떤걸 써야할지 막막해졌습니다ㅠㅠ
    Stoer&Wagner min cut정도를 찾아봤는데,
    더 많이 쓰이는 게 있을까요?


    10년 전
2개의 댓글이 있습니다.
  • kcm1700
    kcm1700

    Dinic 알고리즘이 간편하면서도 빨라요. push relabel 알고리즘은 조심스레 여러가지 휴리스틱을 적용하면 더 빨라질 수 있지만 해야할 게 많아서...

    로컬에서 돌려보니 1분이 넘게 걸리네요. 효율적인 Edmonds-Karp 구현이면 통과하기를 의도했고, 10초 정도 걸리는 경우가 많아서 20초로 잡았어요.


    10년 전 link
  • restart
    restart

    제 Edmonds-Karp는 충분히 효율적이지 않았나 봅니다ㅠ.ㅠ 빠른 답변 정말 감사드려요. 이제 Dinic을 공부해야 겠군요@.@


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.