글 읽기 - 포드 풀커슨으로 풀어봤지만 계속 시간초과가 발생합니다..

redpigeon 4년 전 0

2191번 들쥐의 탈출과 비슷한 문제인 것 같아서, 그때 사용했던 포드-풀커슨 알고리즘 기반의 코드를 작성해봤습니다만..

작은 데이터셋에서도 시간초과가 발생해버립니다.

단순히 BFS로 바꿔서 에드먼드-카프 알고리즘이 되면 통과할 수 있을까요?ㅠㅠ

당최 왜 통과를 못하는지 모르겠습니다ㅠㅠㅠ

서브태스크2는 언감생심이고.. 1이나 통과했으면 좋겠네요ㅠㅠㅠㅠㅠㅠ

import sys

def deep(here):
    global driver
    if driver[here]:
        return False
    
    driver[here] = True

    for there in available[here]:
        if from_where_to[there] == -1 or deep(from_where_to[there]):
            from_where_to[there] = here
            return True

    return False


for _ in range(int(sys.stdin.readline())):
    N, M = map(int, sys.stdin.readline().split())
    X = list(map(int, sys.stdin.readline().split()))
    R = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

    available = [[] for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if R[j][0] <= X[i] <= R[j][1]:
                available[i].append(j)

    from_where_to = [-1]*N
    ans = 0
    for i in range(N):
        driver = [False]*M
        if deep(i):
            ans += 1

    print(ans)

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

문제

문제

출처

ICPC

포드 풀커슨으로 풀어봤지만 계속 시간초과가 발생합니다..

redpigeon 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말