글 읽기 - 노트북을 찾아라 런타임

didwlvv 7년 전 0

보통 런타임이 배열 접근이 잘못되면 뜨는걸로 알고있는데 배열크기를 늘려봐도 에러가 뜹니다. 답은 잘나오는데 먼지 잘 모르겠어요 도와주세요

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;
vector<int>v[6005];
int n,m,sink,source;
int flow[6005][6005];    int capacity[6005][6005];  int p[6005];
void init();    void solve();

int main(){
    
    init();
    solve();
    
    return 0;
}

void init(){
    scanf("%d %d", &n, &m);
    
    for(int i=1; i<=n; i++){
        v[0].push_back(i);
        v[i].push_back(0);
        capacity[0][i]=1;
    }
    
    for(int i=1; i<=m; i++){
        v[n+m+1].push_back(n+i);
        v[n+i].push_back(n+m+1);
        capacity[n+i][n+m+1]=1;
    }
    
    for(int i=1; i<=m; i++){
        int a,b;
        scanf("%d %d", &a, &b);
        v[a].push_back(n+b);
        v[n+b].push_back(a);
        capacity[a][n+b]=1;
    }
}

void solve(){
    int res=0;
    sink= n+m+1;
    
    while(1){
        queue<int>q;
        memset(p,-1,sizeof p);
        p[source]=source;
        
        q.push(source);
        
        while(!q.empty() && p[sink] == -1){
            int now = q.front();    q.pop();
            
            for(int i=0; i<v[now].size(); i++){
                int next = v[now][i];
                
                if(capacity[now][next] - flow[now][next] > 0 && p[next] ==- 1){
                    p[next]=now;
                    q.push(next);
                }
            }
        }
        
        if(p[sink] == -1)break;
        int amount =0x3f3f3f3f;
        for(int i=sink; i !=source; i =p[i]){
            amount = min(amount,capacity[p[i]][i] - flow[p[i]][i]);
        }
        
        for(int i=sink; i !=source; i=p[i]){
            flow[p[i]][i] +=amount;
            flow[i][p[i]] -=amount;
        }
        res +=amount;
    }
    
    cout <<res <<endl;
}

bupjae 7년 전 0

int flow[6005][6005] 에서 필요한 메모리의 양은 6005 * 6005 * 4 = 약 137MB 로, 문제에서 주어진 메모리 제한을 넘어섭니다.

didwlvv 7년 전 0

제가 5105로 타이트하게 줄였는데도 같네요 ㅜㅜ

bupjae 7년 전 0

5105로 줄였다면 flow 가 약 100MB 소모하는데

capacity도 마찬가지로 100MB 소모하게 될 것이고

v 의 경우는 vector의 내부 구조에 따라 많이 달라지겠지만 마찬가지로 2차원 배열이라는 점에서 비슷한 메모리를 필요로 하지 않을까 생각됩니다

didwlvv 7년 전 0

아 배열 하나당이였네요. 한번 해보겠습니다.

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

문제

문제

출처

ICPC

노트북을 찾아라 런타임

didwlvv 7년 전 0

bupjae 7년 전 0

didwlvv 7년 전 0

bupjae 7년 전 0

didwlvv 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말