本题关联比赛
20120711

关于 Redundant Paths 的近10条评论(全部评论)
多年前完全不会做的题目。。之前分析了好久奇节点偶节点，怎么分析都分析不对QAQ 果然要看书 HouJikan 2014-12-12 16:43 1楼

869. [USACO Jan06]Redundant Paths

★★★ 输入文件：rpathsa.in 输出文件：rpathsa.out 简单对比
时间限制：1 s 内存限制：128 MiB

跟 cogs311. [USACO Jan06 Gold] 冗余路径重题

有F (1 <= F <= 5,000)个牧场(标号为：1..F)。奶牛们厌倦了老是走重复的路径。它们想在牧场之间建立一些新的边，使得任意两个牧场至少有两条不同的路径。现在不同的牧场之间已经至少有一条路径了。

给出R (F-1 <= R <= 10,000)条边，每条边连接两个不同的牧场。计算最少需要建立多少条边，使得任意两个牧场之间至少有两条不同的路径。只要没有访问相同的边,那么就可以认为是不同的路径，就算是访问的中间牧场有相同.

注意：两个不同的牧场之间可能有多条不同的边,你依然可以在这两个牧场间建立一条不同的新边。

输入格式：

*第1行:两个不同的整数: F、R

*第2..R+1行:每行两个不同的牧场，表示它们之间有一条边。

输入解释：

   1   2   3
   +---+---+ 
       |   |
       |   |
 6 +---+---+ 4
      / 5
     /
    /
 7 +

样例输入：rpathsa.in

输出格式：

*一行: 一个整数，算最少需要建立多少条新边，使得任意两个牧场之间至少有两条不同的路径。

样例输出：rpathsa.out

输出解释：

在牧场1和6之间建立一条新边，在牧场4和7之间建立一条新边.

以下是部分路径（左边是牧场，右边是不同的路径）:

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

你可以发现，任意两个不同牧场之间都至少有两条不同的路径。

   1   2   3
   +---+---+ 
   :   |   |
   :   |   |
 6 +---+---+ 4
      / 5  :
     /     :
    /      :
 7 + - - - -