글 읽기 - 메모리 초과 이유가 무엇인가요?

kth990303 3년 전 0

안녕하세요

1658 돼지잡기 문제를 풀다가 메모리초과가 떠서 질문드립니다.

최대 크기는 1001*101이면 충분할 듯 하고,

Source->돼지우리, 날짜에 따른 돼지우리 개수 생성, 돼지우리->사람, 사람->Sink 연결을 다 해주었으며, (즉, 정점이 M*N+N+1개입니다.)

열쇠를 공유하고 있는 돼지 우리끼리도 이동이 가능해야되므로 벡터를 추가로 생성하여 코드를 아래와 같이 짜보았는데,

메모리 초과가 떠서 막막한 상황입니다.

최대한 코드에 주석을 상세히 달았습니다 ㅠㅠ 아예 로직을 뜯어 고쳐야 될까요..?

도움 부탁드립니다. 감사합니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX = 101 * 1001;
const int INF = 1000000007;
int ans, N, M;
// 구조체를 만들어서 진행
struct Edge {
	int to, c, f;
	Edge* rev;
	Edge() :Edge(-1, 0) {}
	Edge(int to1, int c1)
		:to(to1), c(c1), f(0), rev(nullptr) {}
	int remain() {
		return c - f;
	}
	void push(int x) {
		f += x;
		rev->f -= x;
	}
};
vector<Edge*> v[MAX];
inline void addEdge(int a, int b, int c) {
	Edge* e1 = new Edge(b, c);
	Edge* e2 = new Edge(a, 0);
	e1->rev = e2;
	e2->rev = e1;
	v[a].push_back(e1);
	v[b].push_back(e2);
}
// 전형적인 네트워크 플로우
void maxFlow(int s, int e) {
	while (1) {
		int prev[MAX];
		Edge* path[MAX] = { 0 };
		fill(prev, prev + MAX, -1);
		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (auto i : v[x]) {
				int next = i->to;
				if (i->remain() > 0 && prev[next]==-1) {
					q.push(next);
					prev[next] = x;
					path[next] = i;
					if (next == e)
						break;
				}
			}
		}
		if (prev[e] == -1)
			break;
		int flow = INF;
		for (int i = e; i != s; i = prev[i]) {
			flow = min(flow, path[i]->remain());
		}
		for (int i = e; i != s; i = prev[i]) {
			path[i]->push(flow);
		}
		ans += flow;
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
    
    // N: 사람, M: 돼지 우리
	cin >> N >> M;
    // Source: 0, Sink: M*N+N+1, 돼지 우리: 1~M
    // 사람: M*N+(1~N)
    // 소스->돼지우리
	for (int i = 1; i <= M; i++) {
		int j;
		cin >> j;
		addEdge(0, i, j);
	}
    //돼지우리->다음날 돼지우리 (용량은 INF)
    //예제에서는 1->4, 2->5, 3->6, 4->7,...
	for (int j = 2; j <= N; j++) {
		for (int i = 1; i <= M; i++) {
			int s = (j - 2) * M + i;
			int num = (j - 1) * M + i;
			addEdge(s, num, INF);
		}
	}
    //그 외 작업
	for (int i = 1; i <= N; i++) {
		int cnt;
		cin >> cnt;
        // key의 위치 저장을 위한 벡터
        // 예제대로라면 벡터엔 1,2,4,5가 저장돼서 1->5, 2->4가 되도록
		vector<int> k(cnt * 2, 0);
		for (int j = 1; j <= cnt; j++) {
			int key;
			cin >> key;
			k[j - 1] = key + M * (i - 1);
			k[j - 1 + cnt] = key + M * i;
			int s = M * (i - 1) + key;
			int e = M * N + i;
			// key를 가진 돼지우리에서 사람까지
			addEdge(s, e, INF);
		}
        // key를 가진 것 끼리 교차연결
		for (int j = 0; j < cnt; j++) {
			for (int p = cnt; p < cnt * 2; p++) {
				if (p - j == cnt)
					continue;
				addEdge(k[j], k[p], INF);
			}
		}
        // 혹시 몰라서 벡터 초기화...하면 MLE 안뜰 줄 알았는데 뜸..
		k.clear();
		// 사람에서 싱크까지 연결
		int num;
		cin >> num;
		int start = M * N + i;
		int end = M * N + N + 1;
		addEdge(start, end, num);
	}
    // 전형적인 네트워크플로우
	maxFlow(0, M * N + N + 1);
	cout << ans << "\n";
}

sky 3년 전 0

지금 MLE때문에 문제가 발생하신거면 Edge를 너무 많이 만들고 있지않나 생각해보셔요

저 같은 경우엔 이중포문(n^2)으로 key가 있는 우리끼리 연결하니까 이론상 노드개수 10만개 * 우리개수 1000개 해서 MLE로 고생했었는데

조금생각해보니 불필요한 Edge를 줄일 수 있었어요

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

문제

문제

출처

ICPC

메모리 초과 이유가 무엇인가요?

kth990303 3년 전 0

sky 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말