글 읽기 - 축사배정 코드 왜 시간초과인지 모르겠습니다...

hun3555 4년 전 0

제목에 적힌 대로 시간초과가 나는 코드입니다.

사용한 알고리즘은 호프크로프트-카프 알고리즘이고, 검색을 통해 찾아본 소스코드를 거의 그대로 구현했습니다.

그런데 시간초과가 나서 해결이 안 되더군요. 처음에는 iostream을 이용해 입력을 받았어서 그 문제인가 싶어서 stdio.h를 이용하게 바꾸었는데도 시간초과가 납니다.

몇 번 읽어봤는데도 어째서 시간초과가 나는지 감도 못 잡겠습니다 도와주세요...

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 202;
const int INF = 1000;

int N, M, A[MAX], B[MAX], dist[MAX];
bool used[MAX];
vector<int> adj[MAX];

void bfs(){
    queue<int> Q;

    for(int i = 0; i < N; i++){
        if(!used[i]){
            Q.push(i);
            dist[i] = 0;
        }
        else dist[i] = INF;
    }

    while(!Q.empty()){
        int a = Q.front();
        Q.pop();
        for(int b: adj[a]){
            if(B[b] != -1 && dist[B[b]] == INF){
                dist[B[b]] = dist[a]+1;
                Q.push(B[b]);
            }
        }
    }
}

bool dfs(int a){
    for(int b: adj[a]){
        if(B[b] == -1 || (dist[B[b]] == dist[a]+1 && dfs(B[b]))){
            used[a] = true;
            B[b] = a;
            A[a] = b;
            return true;
        }
    }
    return false;
}

int main(){
    scanf("%d %d", &N, &M);

    for(int i = 0; i < N; i++){
        int si, ho;
        scanf("%d", &si);
        for(int j = 0; j < si; j++){
            scanf("%d", &ho);
            adj[i].push_back(ho-1);
        }
    }

    int match = 0;
    fill(A, A+N, -1);
    fill(B, B+M, -1);

    while(true){
        bfs();

        int flow = 0;
        for(int i = 0; i < N; i++){
            if(!used[i] && dfs(i)) flow++;
        }

        if(flow == 0) break;
        match += flow;
    }

    printf("%d\n", match);
    return 0;
}

hun3555 4년 전 0

제출 언어 미스였네요... C++17로 제출하니 통과되었습니다

djm03178 4년 전 0

네, range based for는 C++11에서 만들어진 것이기 때문에 더 오래된 버전인 그냥 C++로는 27번째 줄이 제대로 동작하지 않습니다. 사실 저게 왜, 어떤 방식으로 컴파일이 되는지도 모르겠습니다.

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

문제

문제

출처

ICPC

축사배정 코드 왜 시간초과인지 모르겠습니다...

hun3555 4년 전 0

hun3555 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말