Please read the new rule regarding the restriction on the use of AI tools. ×

darkprinx's blog

Need help for LightOj 1308 — Ant Network
By darkprinx, history, 8 years ago, In English

Hello, I'm recently trying to understand this problem 1308 — Ant Network . I'm quite confused with a input that I saw in forum post that is

Input
1
5 5
0 1
1 2
2 3
3 4
4 0

Output
Case 1: 2 10

I have read the explanation about this case which was given by Leonardo Boshell. But still unable to understand how this output comes. Can anyone please explain me in details. It will be very helpful to me. Thanks in advance :)

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

Comments Comments (1)
| Write comment?
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

One escape node isn't enough: if the earthquake destroys it, the other ants cannot get to an escape node.

Two escape nodes is enough: if the earthquake destroys one, the other is always reachable by the ants. How many ways to do this? There are 5 nodes and we need to choose 2: 5C2=10.

→ Reply