Graph Olympiad Problem

Правка en2, от MODDI, 2022-08-11 20:37:54

Given a weighted undirected graph with N nodes and N-1 edges, we are also given S special nodes. For each special node, there is a convoy that is sent to the furthest node for each Si (if there are ties, the ending node is chosen at random). We are asked to find the maximum number of convoys that can't reach their target nodes if we remove one node from the graph and the number of ways to achieve this.

Example:

N = 4
0 1 3
1 2 10
1 3 11
S = 3
0 2 3
Ans: 3 1

We have 3 convoys({0 -> 3}, {2 -> 3}, {3 -> 2}), each of the convoys passes through node 1, so if we remove this node we have 3 convoys that can't get to their ending node, and the number of ways to do this is 1.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский MODDI 2022-08-11 20:37:54 9
en1 Английский MODDI 2022-08-09 03:13:33 718 Initial revision (published)