글 읽기 - 11111번 두부장수 장홍준 2 문제 런타임 에러 질문입니다.

kks227 7년 전 0

체크판 무늬처럼 두부 모판을 두 그룹으로 나누는데,

시작점 그룹에 속한 정점은 자신의 인접한 두부 중 하나와 짝을 지을 수 있고

아닐 경우 그냥 도착점 그룹으로 유량을 보내서(실패)

항상 총 NM/2의 유량을 도착점으로 보내도록 하며 MCMF로 최대 두부 가격 합을 구했는데요.

따라서 총 정점 개수는 최대 NM+2(source, sink)개입니다.

제 컴퓨터에서는 예제라던가, 50*50짜리 케이스에서도 답이 잘 나오고 1*1짜리에서도 답이 잘 나왔는데

알 수 없는 이유로 계속해서 런타임 에러가 뜨네요. 혹시 메모리 초과일까요?

혹시 원인을 아시겠거나, 아니면 비슷한 경험이 있으신 분들은 답변 부탁드립니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N = 50;
const int MAX_V = MAX_N*MAX_N+2;
const int S = MAX_V-2;
const int E = MAX_V-1;
const int INF = 1000000000;
const int roff[4] = {-1, 1, 0, 0};
const int coff[4] = {0, 0, -1, 1};
const int val[6][6] = {
	{10, 8, 7, 5, 0, 1},
	{8, 6, 4, 3, 0, 1},
	{7, 4, 3, 2, 0, 1},
	{5, 3, 2, 2, 0, 1},
	{0, 0, 0, 0, 0, 0},
	{1, 1, 1, 1, 0, 0}
};

inline int nodeNum(int r, int c){ return r*MAX_N+c; }

int main(){
	int N, M, grade[MAX_N][MAX_N];
	// c: capacity, d: cost, f: current flow
	int c[MAX_V][MAX_V] = {0}, d[MAX_V][MAX_V] = {0}, f[MAX_V][MAX_V] = {0};
	scanf("%d %d\n", &N, &M);
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++)
			grade[i][j] = getchar() - 'A';
		getchar();
	}

	// 그래프 만듦
	vector<int> adj[MAX_V];
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			int curr = nodeNum(i, j);
			
			// 이분 매칭: 시작점 쪽 정점
			if(i%2 == j%2){
				c[S][curr] = 1;
				adj[S].push_back(curr);
				adj[curr].push_back(S);

				// 인접한 4방향
				for(int k=0; k<4; k++){
					int ni = i + roff[k];
					int nj = j + coff[k];
					if(ni<0 || ni>=N || nj<0 || nj>=M) continue;

					// 맞는 범위 안일 경우 cost가 있는 간선 추가
					int next = nodeNum(ni, nj);
					c[curr][next] = 1;
					// 최대 cost를 찾아야 하므로 간선 cost 부호가 반대
					d[curr][next] = -val[grade[i][j]][grade[ni][nj]];
					d[next][curr] = val[grade[i][j]][grade[ni][nj]];
					adj[curr].push_back(next);
					adj[next].push_back(curr);
				}
			}

			// 시작점 쪽이건 도착점 쪽이건 도착점으로 가는 간선 추가
			// 시작점 쪽 노드에서 가는 간선은 실패간선(버리는 한 칸짜리 두부)
			c[curr][E] = 1;
			adj[curr].push_back(E);
			adj[E].push_back(curr);
		}
	}

	// MCMF
	int result = 0;
	while(1){
		int prev[MAX_V], dist[MAX_V];
		bool inQ[MAX_V] = {0};
		queue<int> Q;
		fill(prev, prev+MAX_V, -1);
		fill(dist, dist+MAX_V, INF);
		dist[S] = 0;
		inQ[S] = true;
		Q.push(S);

		// SPFA
		while(!Q.empty()){
			int curr = Q.front();
			Q.pop();
			inQ[curr] = false;
			for(int next: adj[curr]){
				if(c[curr][next]-f[curr][next] > 0 && dist[next] > dist[curr]+d[curr][next]){
					dist[next] = dist[curr] + d[curr][next];
					prev[next] = curr;
					if(!inQ[next]){
						Q.push(next);
						inQ[next] = true;
					}
				}
			}
		}
		if(prev[E] == -1) break;

		// 유량은 반드시 1. 이번에 찾은 경로만큼 두부가격 합 더함
		for(int i=E; i!=S; i=prev[i]){
			result -= d[prev[i]][i];
			f[prev[i]][i]++;
			f[i][prev[i]]--;
		}
	}
	printf("%d\n", result);
}

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

문제

문제

출처

ICPC

11111번 두부장수 장홍준 2 문제 런타임 에러 질문입니다.

kks227 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말