글 읽기 - 1005번 반례

minu0122 6년 전 0

게시판을 읽어보면서 많은 수정을 했습니다

하지만 33프로에서 틀렸다고 나오는데 반례좀 알려주시면 감사하겠습니다.

DFS로 풀었습니다

#include <iostream>
#include <algorithm>

using namespace std;

int tree(int node[1000][1000], int x, int d[1000], int n);

int main()
{
	int t, n, k, d[1000], node[1000][1000], a, b, x;
	cin >> t;
	while (t--)
	{
		cin >> n >> k;
		for (int i = 0; i < n; i++)
			cin >> d[i];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
				node[i][j] = 0;
		}
		for (int i = 0; i < k; i++)
		{
			cin >> a >> b;
			node[b - 1][a - 1] = 1;
		}
		cin >> x;
		cout << tree(node, x - 1, d, n) << endl;
	}
}

int tree(int node[1000][1000], int x, int d[1000], int n)
{
	bool done = false;
	int max = 0, path[1000], level = 0, num;
	path[0] = x;
	while (!done)
	{
		for (int i = 0; i < n; i++)
		{
			if (node[path[level]][i] == 1)
			{
				level++;
				path[level] = i;
				i = -1;
			}
		}
		num = 0;
		for (int i = 0; i <= level; i++)
			num += d[path[i]];
		if (max < num)
			max = num;
		level--;
		node[path[level]][path[level + 1]] = 0;
		done = true;
		for (int i = 0; i < n; i++)
		{
			if (node[x][i] == 1)
				done = false;
		}
	}
	return max;
}

minu0122 6년 전 0

4 3

10 1 100 10

1 2

2 3

2 4

3 4

라는 반례가 있어서 코드를 고쳤는데 이번엔 시간초과라고 뜨네요;;

#include <iostream>

using namespace std;

int tree(int node[1000][1000], int x, int d[1000], int n);

int main()
{
	int t, n, k, d[1000], node[1000][1000], a, b, x;
	cin >> t;
	while (t--)
	{
		cin >> n >> k;
		for (int i = 0; i < n; i++)
			cin >> d[i];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
				node[i][j] = 0;
		}
		for (int i = 0; i < k; i++)
		{
			cin >> a >> b;
			node[b - 1][a - 1] = 1;
		}
		cin >> x;
		cout << tree(node, x - 1, d, n) << endl;
	}
}

int tree(int node[1000][1000], int x, int d[1000], int n)
{
	bool in;
	int max = 0, path[1000], level = 0, num;
	for (int i = 0; i < n; i++)
		path[i] = -1;
	path[0] = x;
	while (level > -1)
	{
		in = false;
		for (int i = path[level + 1] + 1; i < n; i++)
		{
			if (node[path[level]][i] == 1)
			{
				level++;
				path[level] = i;
				i = -1;
				in = true;
			}
		}
		if (in)
		{
			num = 0;
			for (int i = 0; i <= level; i++)
				num += d[path[i]];
			if (max < num)
				max = num;
		}
		path[level-- + 1] = -1;
	}
	return max;
}

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

문제

문제

출처

ICPC

1005번 반례

minu0122 6년 전 0

minu0122 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말