Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize. ×

Graph Problem

Revision en1, by MODDI, 2022-08-09 03:13:33

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.


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. 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)