关于神秘的挤奶机的近10条评论(全部评论)
表示prime什么的根本就不会，只好用二分了。。 _Itachi 2016-11-07 06:35 11楼
在百练上看到这题……一遍Prim上去……WA了……发现加流和退流没有分开做……简直身败名裂 mildark 2016-08-28 18:52 10楼
= =跑K遍spfa是不是有点慢啊 HouJikan 2014-09-19 15:39 9楼
回复 @高高高高高2333333333 : 神犇为何要卖萌…… cstdio 2014-05-05 20:27 8楼
回复 @cstdio : 大神，用最小生成树怎么写呢？ , 2014-05-05 19:51 7楼
回复 @cstdio : 最小生成树只会并查集,不会prim,不知道Prim还有这个特效 Chenyao2333 2014-04-17 12:23 6楼
回复 @Chenyao : 额，你不觉得这个题要求的非常像最小生成树吗 cstdio 2014-04-16 22:13 5楼
回复 @cstdio : 等等等等...........最小生成树?这题不是最小费用流么? Chenyao2333 2014-04-16 18:59 4楼
回复 @Chenyao : 壮士你是怎么用SPFA写最小生成树的？ cstdio 2014-04-16 15:07 3楼
回复 @cstdio : 我脑洞太大了,一开始竟然用二分,难道dij比spfa快(感觉是代码哪里搓了),还有神犇的dij注释中加流和退流那两行我没有看懂,为什么要这样写? Chenyao2333 2014-04-16 13:45 2楼

1595. [USACO Feb05] 神秘的挤奶机

★★★☆ 输入文件：secretmilking.in 输出文件：secretmilking.out 简单对比
时间限制：3 s 内存限制：256 MiB

约翰正在制造一台新型的挤奶机，但它不希望别人知道。他希望尽可能久地隐藏这个秘密。他把挤奶机藏在他的农场里，使它不被发现。在挤奶机制造的过程中，它需要去挤奶机所在的地方T（1<=T<=200）次。他的农场里有秘密的地道，但约翰只在返回的时候用它。

农场被划分成N（2<=N<=200）块区域，用1到N标号。这些区域被P（1<=P<=40000）条双向道路连接。每条路有一个小于10^6的长度L，两块区域之间可能有多条道路连接。

为了减少被发现的可能，约翰不会两次经过农场上的任何一条道路。当然了，他希望走最短的路。

请帮助约翰寻找这T次从仓库走到挤奶机所在地的路线。仓库是区域1，挤奶机所在地是区域N。我们现在要求的是约翰经过的这些道路中最长的路的长度最小是多少，当然他不能重复走某一条路。请注意，我们要求的不是最短的总路程长度，而是所经过的直接连接两个区域的道路中最长的道路的最小长度。

数据保证约翰可以找到T条没有重复的从仓库到挤奶机所在区域的路。

第1行是3个整数N,P和T，用空格隔开。

第2到P+1行，每行包括3个整数，Ai,Bi,Li，表示区域Ai,Bi之间有一条长度为Li的道路。

输出只有一行，包含一个整数，即约翰经过的这些道路中最长的路的最小长度。

约翰选择1-2-3-7和1-6-7两条路线。这些路线中最长路的最小长度是5.

USACO FEB05 Silver

Vladimir Novakovski, 2003

Translate by: 庄乐