글 읽기 - 엥? 그냥 간단한 위상정렬 아닌가요?

d252b 6년 전 0

어느 케이스에서 틀렸는지 답답하네요.

그냥 평범함 위상정렬 문제 같은데...

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
vector<int> arr;
vector<int> dist;
vector<int> sol;
int T;
void we();
vector<vector<int> >  soon;
int main()
{
	scanf("%d", &T);
	arr.resize(T + 1, 0);
	dist.resize(T + 1, 0);
	soon.resize(T + 1);
	sol.resize(T + 1,0);
	for (int i = 1; i <= T; i++)
	{
		scanf("%d", &arr[i]);
		while (1)
		{
			int a;
			scanf("%d", &a);
			if (a == -1)
				break;
			soon[a].push_back(i);
			dist[i]++;
		}
	}
	we();
}
void we()
{
	queue<int> q;
	
	for (int i = 1; i <= T; i++)
	{
		if (dist[i] == 0)
		{
			q.push(i);
			sol[i] = arr[i];
		}
	}

	while (!q.empty())
	{
		int here = q.front();
		q.pop();
		for (int i = 0; i < soon[here].size(); i++)
		{
			dist[soon[here][i]]--;
			if (dist[soon[here][i]] == 0)
			{
				q.push(soon[here][i]);
				sol[soon[here][i]] += sol[here] + arr[soon[here][i]];
			}
		}
	}
	for (int i = 1; i < sol.size(); i++)
	{
		printf("%d\n", sol[i]);
	}
	
	
}

khj94811 6년 전 0

반드시 indegree가 0이 되지 않더라도 건물이 완료되는 시간에 관여할 수 있습니다.

d252b 6년 전 0

그게 무슨 말씀이신지 잘 이해가 안되네요

어떤 건물과 관련이 있을 경우, 차수의 증가,감소 통해서 컨트롤 하게 되는데,

차수가 0이 되지 않는 상황에서 다른 건물에 영향을 준다는 게 어떤 의미인가요??

차수에 각 건물끼리 서로에 대한 영향이 반영되어 있지 않나요?

khj94811 6년 전 0

A를 만들기 위해서 B와 C를 모두 만들어야 한다면 B와 C가 모두 A에 영향을 주겠죠??

하지만 님의 코드를 보면 B와 C중 A의 진입차수를 0을 만들게 되는 건물에 한해서만 영행을 주게 되어있습니다

poia0304 6년 전 5

만약 A,B가 끝나는 시간이 다르다면 둘 중 늦게 끝나는 시간 + C를 짓는데 걸리는 시간이 답이 되어야 합니다.

하지만 위 소스 대로라면 A,B중 만약 B가 시간이 더 오래 걸린다고 할 때, B가 먼저 건설된 뒤, A가 건설된다면 C를 짓는데 걸리는 시간은 A+C시간이 됩니다.

따라서 우선순위 큐를 통해 A가 먼저 건설된 뒤, B가 건설 되도록 해줘야 합니다.

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

문제

문제

출처

ICPC

엥? 그냥 간단한 위상정렬 아닌가요?

d252b 6년 전 0

khj94811 6년 전 0

d252b 6년 전 0

khj94811 6년 전 0

poia0304 6년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말