为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。

USACO/butter

来自NOCOW
跳转到： 导航, 搜索
这是USACO Chapter 3 .2中的OI题目Sweet Butter的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

这是NOCOW内容页面。

相关讨论请到本文的讨论页，谢谢合作！

目录

[编辑] 分析

此题的实际模型如下：给定一个有P个顶点的无向图，选择一个顶点，使得从该点到给定的N个顶点的权值之和最小。

[编辑] Hint

一定要记得用邻接表存图 记住每个点不止有一只牛，算出点的距离还要乘以牛的数量

用最小堆来优化SPFA的注意，如果对点v松弛成功，无论点v在不在堆中都要插入堆，否则算法是错误的。

[编辑] Bellman-Ford算法

数据规模中边数小于1450，使用Bellman-Ford求一次单源最短路的复杂度为O(e*k)，k为一个小常数，总复杂度也就是O(n*e*k)。

d数组储存最短路长，Bellman算法的思想就是对每条边进行松弛，因为一共n个点，所以这种松弛操作最多执行n次后，d数组的值就不会再改变。

还需要用一个布尔变量记录这次操作中是否产生了更小的最短路，如果没有，说明d数组中值已为最优，不需要再操作，直接退出。这样做或许时间上还是有点问题，便可以用SPFA优化。

SPFA就是指每次松弛操作时记录哪些点更新了最短路值，将这些点加入数组，下次只对这些点关联的边进行松弛。进一步降低了复杂度。实现SPFA需要用邻接表储存边。

最后统计一次带权路径长，进行n次Bellman-Ford操作后得出结果。运行时间都在0.4秒以内。 --By Yangjhjh 07.08.11


建议习惯数组模拟指针的（也最好）使用前向星优化，这样可以保证没有用邻接矩阵实现Bellman-Ford时的O(n^3)的复杂度（退化成Floyd了），也可以降低用数组模拟临界表所需的内存，保证严格做到Bellman-Ford的标准复杂度O(NE),再加上以每个顶点做出发点循环一次，总复杂度为O(n^2*E)。

但是，用裸的Bellman-Ford还是慢了，采取上面提到的优化（每进行一圈的松弛检查，如果没有任何松弛操作就跳出Bellman-Ford）就可以了，完全够了，可以控制到0.25S以内。（这也是Bellman-Ford在这一题时间复杂度上似乎劣于Floyd，实际可以跑得比Floyd好的原因——Floyd是极难优化的，本题能够过掉8个点就不错了；Bellman-Ford加上最朴素的优化后可以大大降低无效操作数）

[编辑] Dijkstra算法

求每对顶点之间的最短路径首先想到的便是Floyd算法:但P的范围是（P<=800）则时间复杂度为O(800^3)，显然会超时。此时可以考虑使用Dijkstra算法求最短路径（Dijkstra是O(N^2)的算法），但直接使用Dijkstra仍然会超时O(800*800^2)=O(800^3)，此时可以用堆进行优化。

Dijkstra算法每次都需要在Dist[]数组中寻求一个最小值，如果图很大，则在此处花费的时间会很多，而堆则可以在O(1)的时间内马上求得最小值，并且维护一个堆所需的时间都是在log级的。因此考虑把Dist[]数组的值用堆来存储。

为了记录堆中的每一个元素是源点与哪个顶点的，可以增加了一个point变量，用来记录这条边所连接的另一个顶点。

用堆操作的Dijkstra的思想还是与一般的思想类似(在OIBH上找了一些信息)：

初始化Dist[]=MAX，然后将源点t放入堆中(这就与Dist[t]=0类似),再从堆中找出一个最小值没有被确定的点minp(就是Dist[minp]=MAX)，将其确定下来(Dist[minp]=mins,mins为从堆中取出来的那个最小值)，接着由这个最小值所连接的点求出从源点到这些点的路径长，若所连接的点没有求出最小值(Dist[i]=MAX)，则将这个点放入堆中(这就好比用for循环去修改每一个Dist[]的值,不同的地方在于堆中存放的是源点到各个顶点的最小值，如果刚求出来的顶点在Dist[]中已经被赋值了，说明求出来的肯定不是最小值，就像普通Dijkstra的Mark[]一样，mark过的点是不能再被计算的，所以不能放Dist[]中有值的点。)这样Dijkstra的部分就完成了。

仔细观察了一下N<=800，而道路数C<=1450。800*800=640000与1450的差距实在是大……可以改用存边的方式(同时保留邻接矩阵，这样可以很方便地知道两点之间的权值)，用一个二维的数组便可以存下边的信息。

补充：用STL中的priority_queue优化dijkstra编程复杂度更小！ 可以用vector代替数组实现前向星

[编辑] SPFA算法

对于枚举的每个牧场i，用SPFA求出到每个点的最短路如下：dist[j]表示i->j的距离，初始值为maxint，其中dist[i]=0。维护一个队列，初始为q[1]=i;由队首枚举其他的牧场j更新牧场i到j的最短距离并同时拓展队列。直到队列空为止。这样就求出了点i到所有点的最短距离。

SPFA的优化：

如果枚举到的牧场i，那么以表明1--i-1牧场为源点的最短路都已经求出过，也就是说i牧场到1--i-1中任一牧场最短路已知， 用这个已知条件来初始化dist[1]--dist[i-1]这样效率会有很大提升。注意：如果min[j,k]表示j到k的最短路，在以k点 为源点并进行上述优化时，应将dist[k]:=min[j,k]+1，而不是min[j,k]。否则j点不会进入队列，也就无法拓展经过j点的路径。

图的存储：

有人说用邻接表，但是我认为用链式前向星（参见Malash神牛blog）（详见http://malash.me/200910/linked-forward-star/ ）更方便而且省空间。可以在不增加时间复杂度的前提下把空间优化到1000k左右。 我们实际上还可以在链式前向星的基础上再加上SLF+LLL的优化，时间效率飞起来（见pascal)

[编辑] floyd

第一次在这里写题解好激动，其实这个题我本来想测测用Floyd能过几个点，没想到Floyd直接AC了USACO的服务器好强大....... Executing... 

  Test 1: TEST OK [0.011 secs, 5740 KB]
  Test 2: TEST OK [0.000 secs, 5740 KB]
  Test 3: TEST OK [0.011 secs, 5740 KB]
  Test 4: TEST OK [0.011 secs, 5740 KB]
  Test 5: TEST OK [0.011 secs, 5740 KB]
  Test 6: TEST OK [0.032 secs, 5740 KB]
  Test 7: TEST OK [0.151 secs, 5740 KB]
  Test 8: TEST OK [0.389 secs, 5740 KB]
  Test 9: TEST OK [0.896 secs, 5740 KB]
  Test 10: TEST OK [0.886 secs, 5740 KB]

详细代码见mingxiy1 --明溪月 2012年10月21日 (日) 19:00 (CST)

[编辑] 质疑

你提交的时候是不是USACO服务器出BUG了……我自己写的Floyd还加了少许优化， 结果超时，然后用了你的程序，还是超时……难道我这边提交上去USACO就歧视？

floyd同超时！！ --Ciocio

论编译器的偏见性 --Darkdream

哪个lucky dog 用 Floyd过的， 你的程序卡在的第九个点1.069s，纯属扯淡，还是用spfa吧 ——七哥

Floyd 超时+1

呵呵

为什么我自己floyd没任何问题？ 你们大多数应该也是C++啊。。。 虽然比较慢但是还是过了 

  Test 1: TEST OK [0.000 secs, 6708 KB]
  Test 2: TEST OK [0.000 secs, 6708 KB]
  Test 3: TEST OK [0.000 secs, 6708 KB]
  Test 4: TEST OK [0.000 secs, 6708 KB]
  Test 5: TEST OK [0.000 secs, 6708 KB]
  Test 6: TEST OK [0.014 secs, 6708 KB]
  Test 7: TEST OK [0.098 secs, 6708 KB]
  Test 8: TEST OK [0.294 secs, 6708 KB]
  Test 9: TEST OK [0.686 secs, 6708 KB]
  Test 10: TEST OK [0.686 secs, 6708 KB]

[编辑] 参考代码

C

C++

pascal

来自“http://www.nocow.cn/index.php?title=USACO/butter&oldid=36388”
个人工具