P2860 [USACO06JAN] Redundant Paths G
题目描述
In order to get from one of the F (1
输入格式
无
输出格式
无
说明/提示
Explanation of the sample:
One visualization of the paths is:
Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions.
Check some of the routes:
- 1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2
- 1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4
- 3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7
Every pair of fields is, in fact, connected by two routes.
It's possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.