글 읽기 - 런타임 에러가 나는 이유를 모르겠습니다ㅠㅠ

qkrwns1714 4년 전 0

네트워크 플로우로 풀었습니다....

아무리 생각해도 제출하자마자 런타임 에러가 떠 버리는 이유를 모르겠습니다ㅠㅠ

고수분들의 도움의 손길을 기다립니다....

/*
1.
순서대로 번호 붙이기
123
654
789

2.간선 잇기
3.홀수 짝수 나누기(홀수에 sourse, 짝수에 sink 잇기)
4.네트워크 플로우 실행
5.남은 수 구해 정답에 더해주기
*/

#include <bits/stdc++.h>
#include <queue>

using namespace std;

const int MAX = 503;

int n, m;
int gz[53][53];  // 격자
int number[53][53]; // 넘버를 저장할 배열
vector<int> graph[MAX]; // 간선 저장 
int pipe[MAX][MAX]; // 간선의 최대 유량
int npip[MAX][MAX]; // 간선의 현재 유량

void ins(int i, int j, int ii, int jj){ // 간선 저장
   // cout << number[i][j] << " " << number[i+ii][j+jj] << " - " << min(gz[i][j], gz[i+ii][j+jj]) << "\n";
    graph[number[i][j]].push_back(number[i+ii][j+jj]);
    graph[number[i+ii][j+jj]].push_back(number[i][j]);
    pipe[number[i+ii][j+jj]][number[i][j]] = 0;  // 초기화(전 테케의 값이 있을 수 있기 때문에)
    npip[number[i+ii][j+jj]][number[i][j]] = 0;  // 초기화(전 테케의 값이 있을 수 있기 때문에)
    pipe[number[i][j]][number[i+ii][j+jj]] = min(gz[i][j], gz[i+ii][j+jj]); // 둘 중 더 작은 것을 가중치로 설정
    npip[number[i][j]][number[i+ii][j+jj]] = 0;  // 초기화(전 테케의 값이 있을 수 있기 때문에)
}

void pus(int i, int j, int a, int b){ // 홀수와 sourse, 짝수와 sink를 연결
  //  cout << a << " " << b << " " << gz[i][j] << "\n";
    graph[a].push_back(b);
    graph[b].push_back(a);
    pipe[a][b] = gz[i][j];
    pipe[b][a] = 0; // 초기화(전 테케의 값이 있을 수 있기 때문에)
    npip[b][a] = 0; // 초기화(전 테케의 값이 있을 수 있기 때문에)
    npip[a][b] = 0; // 초기화(전 테케의 값이 있을 수 있기 때문에)
}

int nam(int a, int b){
    return pipe[a][b] - npip[a][b]; // 유량 계산
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int t;
    for(cin >> t ; t != 0 ; t--){
        cin >> n >> m;
        for(int i = 0 ; i < MAX; i++){ // 초기화
            graph[i].clear();
        }
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= m ; j++){ // 격자 입력
                cin >> gz[i][j];
            }
        }
        int num = 0; // 마지막 넘버
        for(int i = 1 ; i <= n ; i++){ // 넘버링
            if(i%2 == 1){ // 홀수 번째 줄
                for(int j = 1 ; j <= m ; j++){ // 앞쪽부터 넘버링 1 2 3 4....
                    number[i][j] = ++num;
                }
            }
            else{ // 짝수 번째 줄
                for(int j = m ; j != 0 ; j--){ // 뒷쪽부터 넘버링 ....4 3 2 1
                    number[i][j] = ++num;
                }
            }
        }
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= m ; j++){ // 인접한 곳 간선 연결
                if(number[i][j]%2 == 1){ // 홀수 넘버만 연결
                    if(i != 1)ins(i, j, -1, 0);
                    if(j != 1)ins(i, j, 0, -1);
                    if(i != n)ins(i, j, 1, 0);
                    if(j != m)ins(i, j, 0, 1);
                }
            }
        }
        int value = 0;
        int s = 0, e = num+1;
        for(int i = 1; i <= n ; i++){
            for(int j = 1 ; j <= m ; j++){ // sourse와 홀수, sink 와 짝수 연결
                if(number[i][j]%2 == 1){pus(i, j, s, number[i][j]);}
                else{pus(i, j, number[i][j], e);}
            }
        }
        while(1){ // 네트워크 플로우
            int bumo[MAX];
            fill(bumo, bumo+MAX, -1);
            queue<int> que;
            que.push(s);
            while(bumo[e] == -1 && !que.empty()){
                int now = que.front();
                que.pop();
                for(int i : graph[now]){
                    if(bumo[i] == -1 && nam(now, i) > 0){
                        bumo[i] = now;
                        if(i == e)break;
                        que.push(i);
                    }
                }
            }
            if(bumo[e] == -1)break;
            int maxx = 987654321;
            for(int i = e ; i !=s ; i = bumo[i]){
                maxx = min(maxx, nam(bumo[i], i));
            }
            value += maxx;
            for(int i = e ; i != s ; i = bumo[i]){
                npip[bumo[i]][i] += maxx;
                npip[i][bumo[i]] -= maxx;
            }
        }
        for(int i = 1; i <= n ; i++){ // 남은 수 더하기
            for(int j = 1 ; j <= m ; j++){
                if(number[i][j]%2 == 1){ // 홀수 넘버라면 sourse와 연결되있는 간선의 남은 양을 더함
                    value += nam(s, number[i][j]);
                }
                else{ // 짝수 넘버라면 sink와 연결되있는 간선의 남은 양을 더함
                    value += nam(number[i][j], e);
                }
            }
        }
        cout << value << "\n"; // 출력
    }
    return 0;
}

qkrwns1714 4년 전 0

?? MAX 값을 5000 이상으로 하니까 바로 되네요?? 어째서 MAX가 5000까지 있어야 하나요? 제가 생각하기에는 252가 한계인거 같은데....

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

문제

문제

출처

ICPC

런타임 에러가 나는 이유를 모르겠습니다ㅠㅠ

qkrwns1714 4년 전 0

qkrwns1714 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말