글 읽기 - MCMF에서의 벨만포드 알고리즘

caffeinism7 6년 전 0

원래 코드에서는 update되지 않을 시에 break하는 코드가 없어서 TLE가 계속 나왔는데요. 코드를 여러곳 깔끔하지 않은곳이나 MCMF 알고리즘에서 문제가 생길 요소를 전부 잘라도 계속 문제가 생겨서 벨만포드쪽이 최적하게 안짜여진 것 같아서 이부분을 해결하니까 통과가 되는데 update되지 않을 시 알고리즘을 탈출하는 것이 해당 알고리즘에서 시간을 굉장히 단축시킬만한 요소가 되는것인가요?

for (int k = 0; k < n; k++) {
    bool flag = true;
    for (int i = 0; i < n; i++) {
        if (dist[i] >= MAX_PATH_WEIGHT) continue;

        for (auto it = edges[i].begin(); it != edges[i].end(); ++it) {
            if (dist[it->dest] > dist[it->source] + it->weight) {
                dist[it->dest] = dist[it->source] + it->weight;
                track[it->dest] = it;
                flag = false;
            }
        }
    }
    if (flag) break; //update가 되지 않을 시 break
}

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

문제

문제

출처

ICPC

MCMF에서의 벨만포드 알고리즘

caffeinism7 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말