글 읽기 - 해당 문제 DFS 로 풀어도 시간초과가 발생합니다..

jumpingz 6년 전 0

상황에 따라 BFS 가 좋은 경우도 DFS 가 좋은경우도 있다고 하는데.. 어느 경우에 저 두 자료구조를 사용하는지는 잘 모르겠습니다..

일단 해당문제를 DFS 로 해결했는데 시간초과가 발생하네요..

어느 영역에서 오버헤드가 걸리는지 궁금합니다.

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define INF 99999999

using namespace std;

vector<int> Parent(2002);
vector< vector<int> > v(2002);
int Info[2002][2002];

int Flow(int start, int end);
void DFS(int start);

int main()
{
	int a, b, N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		v[0].push_back(i);
		v[i].push_back(0);
		Info[0][i] = 1;
		Info[i][0] = 0;

		cin >> a;
		for (int j = 0; j < a; j++)
		{
			cin >> b;
			b += 1000;

			v[i].push_back(b);
			v[b].push_back(i);

			Info[i][b] = 1;
			Info[b][i] = 0;
		}
	}

	for (int i = 1001; i <= M + 1000; i++)
	{
		v[i].push_back(M + 1001);
		v[M + 1001].push_back(i);

		Info[i][M + 1001] = 1;
		Info[M + 1001][i] = 0;
	}

	cout << Flow(0, M + 1001);
	return 0;
}

int Flow(int start, int end)
{
	int Min, temp, result = 0;

	while (1)
	{
		fill(Parent.begin(), Parent.end(), -1);
		Min = INF;	DFS(start);

		if (Parent[end] == -1)
			break;

		temp = end;
		while (temp != start)
		{
			Min = min(Min, Info[Parent[temp]][temp]);
			temp = Parent[temp];
		}

		temp = end;
		while (temp != start)
		{
			Info[Parent[temp]][temp] -= Min;
			Info[temp][Parent[temp]] += Min;
			temp = Parent[temp];
		}

		result += Min;
	}

	return result;
}

void DFS(int start)
{
	for (int i = 0; i < v[start].size(); i++)
	{
		if (Info[start][v[start][i]] != 0 && Parent[v[start][i]] == -1)
		{
			Parent[v[start][i]] = start;
			DFS(v[start][i]);
		}
	}
}

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

문제

문제

출처

ICPC

해당 문제 DFS 로 풀어도 시간초과가 발생합니다..

jumpingz 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말