글 읽기 - 메모리초과 원인이 뭘까요...?

show981111 4년 전 0

메모리초과뜨는 이유가 뭘까요.... 도대체 모르겠네요;;

#include <queue>
#include <vector>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#define MAX 5001
#define INF 987654321
using namespace std;
vector<int> graph[MAX];
int flow[MAX][MAX], cap[MAX][MAX], parent[MAX],check[MAX];
stack<int> s;
int maxflow(int start, int end)
{
    int num = 1;
    int res = 0;
    while(1)
    {
        queue<int> q;
        fill(parent, parent + MAX, -1);
        q.push(start);
        
        while(!q.empty() && parent[end] == -1)
        {
            int cur = q.front();
            q.pop();
            
            for(int k = 0; k < graph[cur].size(); k++)
            {
                int child = graph[cur][k];
                if(cap[cur][child] - flow[cur][child] > 0 && parent[child] == -1 && check[a] == 0)
                {
                    q.push(child);
                    parent[child] = cur;
                    if(child == end) break;
                }
            }
        }
        
        if(parent[end] == -1) break;
       
        for(int a = end; a!= start; a = parent[a])
        {
            if(a != end && a!= start) check[a]++;
            s.push(a);
            flow[parent[a]][a]++;
            flow[a][parent[a]]--;
        }
        s.push(start);
        
        res++;
        num++;
    }
    
    return res;
}
int main()
{
    int casenum = 0;
    while(1)
    {
        casenum++;
        memset(check,0,sizeof(check));
        memset(flow,0,sizeof(flow));
        memset(cap,0,sizeof(cap));
        int K,N;
        scanf("%d %d",&K,&N);
        if( K == 0 && N == 0) break;
        for(int i = 0; i <= N + 1; i++)
        {
            graph[i].clear();
        }
        for(int i = 1; i <= N; i++)
        {
            while(1)
            {
                int x;
                char a;
                scanf("%d%c", &x,&a); 
                if(cap[i][x] == 0)
                {
                    graph[i].push_back(x);
                    cap[i][x] = 1;
                }
                if(a == '\n') break;
            }
        }
        
        int total = maxflow(1,2);
        printf("Case %d:\n",casenum);
        if(total < K)
        {
            printf("Impossible\n");
        }else
        {
            for(int j = 1; j <= K; j++)
            {
                while(!s.empty())
                {
                    int t = s.top();
                    s.pop();
                    printf("%d ", t);   
                    if(t == 2) printf("\n");
                }
            }
        }
        
    }

    return 0;
}

djm03178 4년 전 0

flow, cap은 각각이 약 100MB로 합하면 200MB 정도가 됩니다.

kyjlyj 4년 전 1

단위 변화: 비트 -> 바이트 -> 킬로바이트 -> 메가바이트

각 단위가 변할때마다 1024씩 증가하는데 대략 1000씩 증가한다고하고 128메가바이트를 바이트로 바꿔볼게요. 1000*1000*128=128000000, 128000000바이트가 128메가바이트에요.

여기서 int형 배열 1칸 크기가 4바이트니 최대 128000000/4=32000000, 약 32000000칸까지 잡을 수 있는거에요. 근데 배열크기가 5001*5001만 하더라도 5000*5000*4는 1억이라서 메모리 초과가 나는거에요. 정확하지 않을 수도 있으니 참고만 부탁드립니다.

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

문제

문제

출처

ICPC

메모리초과 원인이 뭘까요...?

show981111 4년 전 0

djm03178 4년 전 0

kyjlyj 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말