MODDI's blog

By MODDI, history, 20 months ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it