[ 1 ]  [ 2 ]  [ 3 ]  [ 4 ]  [ 5 ]  [ 6 ]  [ 7 ] 
Programming Problems/Graph

사이클 없는 그래프에서 각 점에의 최대 트래픽 찾기 Q

각 점에서의 최대 트래픽을 구해보자.


ex)


1   2

  5

4   3


의 경우


1 14

2 13

3 12

4 11

5 4가 나와야 한다.


모든 점에서 nearby 점의 값들 중 최대값을 고려하는 듯 한데 이걸 preprocessing으로 풀어서 O(N) 을 만든 것으로 보인다. 그냥 나이브하게 구하면 O(N^2) 알골이 된다.

// preprocess your input graph to the following structure
// node -> hash set of neighbors
// hash set to enable amortized O(1) deletions 
vector<unordered_set<int>> topology(n);
vector<int> metadata(n); // contains the population count
vector<int> current_leaf_set;
int global_sum = 0;
for each node id i in topology{
    if(topology[i].size() == 1 ) current_leaf_set.push_back(i);
	global_sum += metadata[i];
}
int i = 0;
vector<int> sum(n), max(n); // initialize them to zero
while(i < current_leaf_set.size()){
        int node_id = current_leaf_set[i++];
	std::cout << node_id << " : " << (std::max( max[node_id], global_sum - metadata[node_id] - sum[node_id] )) << "\n";
	if( topology[node_id].size() == 0 ) continue; // Thanks @helloru
        int next_node = *(topology[node_id].begin()); // will only have one neighbor
	sum[next_node] += ( metadata[node_id] + sum[node_id]);
	max[next_node] = std::max( max[next_node], ( metadata[node_id] + sum[node_id]) );
	topology[next_node].erase(node_id);
	if( topology[next_node].size() == 1 ) current_leaf_set.push_back(next_node);
}



https://www.careercup.com/question?id=5695046734053376