Graph Olympiad Problem

Revision en2, by 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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English MODDI 2022-08-11 20:37:54 9
en1 English MODDI 2022-08-09 03:13:33 718 Initial revision (published)