USACO/schlnet

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 5 .3中的OI题目Network of Schools的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

正确算法

这是一道收缩强连通分量的题。

该题描述的是一个有向图。我们都知道，在一个有向图强连通分量中从任意一个顶点开始，可以到达强连通分量的每个顶点。由此可以把该题中所有强连通分量收缩成分别一个顶点，则入度为0的顶点就是最少要接受新软件副本的学校。

第二问就是，问至少添加多少条边，才能使原图强连通。也就问在收缩后的图至少添加多少条边，才能使之强连通。

可以知道，"存在一个顶点入度为0或者出度为0"与"该图一定不是强连通的"是等价的命题。为了使添加的边最少，则应该把入度为0顶点和出度为0的顶点每个顶点添加1条边，使图中不存在入度为0顶点和出度为0的顶点。

当入度为0的顶点多于出度为0的顶点，则应添加的边数应为入度为0的顶点的个数。当出度为0的顶点多于出入度为0的顶点，则应添加的边数应为出度为0的顶点的个数。

这样就可以解决问题了。但是不要忘了还有特殊的情况，当原图本身就是强连通分量时，收缩成一个顶点，该顶点入度和出度都为0，但第一问应为1，第二问应为0。

求强连通分量，我用的两遍深搜的Kosaraju算法，时间复杂度为O(n+m)。把找到的每个强连通分量收缩为一的顶点，组成新图。设r(x)为x所在的强连同分量的代表节点，如果原图中存在边e(x,y)，那么新图中有边e(r(x),r(y)) 。然后根据点的邻接关系统计出度和入度即可。

求强连通分量的另一种方法

Sinya觉得写深搜求太麻烦了，所以Sinya就用了另一种求强连通分量的方法。

用floyed算出两点间是否可以互相到达。然后枚举任意两个顶点Vi还有Vj，如果两个点互相可以到达，那么他们就是属于同一个强连通分量了。

虽然是O(n^3)的算法。可是这道题能过。可以大幅降低编程复杂度。

但是Sinya又觉得我们要精益求精，所以大家也要掌握深搜法哦

咦，似乎如果采取Dijkstra算法代替Floyd进行最短路计算的话，

算法的瓶颈就会降到O(n2log2n)哦！

好像比深搜的也差不了多少呀。C++童鞋的便利条件可以大大降低变成复杂度！（by路人甲）

话说自己也是P党。。。

• • • • • • • • • 然而我们可以用Tarjan进行啊********

rt，第一问具体方法和有一道题叫间谍网络一样，第二问可以参考楼上神犇。。。 C++党。。。

旁门左道（注：本菜认为该算法也算是标准算法）

本题我用的是一种非标准算法。不知道为什么对，但是过了。

第一问是求最小点基。这个我是分步骤计算的：

首先，所有入度为0的点肯定要得到软件，因为如果得不到，那么没有别的点来通过网络传输给它。找出所有入度为0的点，把这些点以及他所能到达的点全都作上标记。

对于剩下的点，找出块的个数，这里定义两个点连通当且仅当两个点之间存在路径，不考虑方向。原因很简单，两个点之间只要其中一个能到达另一个即可，这样的块中必然有一个点可以作为起点，而由于前一步已经把入度为0的点去掉了，所以这样的块一定从起点可以到达所有点。

第一问的答案就是上述两者个数之和。

第二问首先统计整个图的入度为0和出度为0的点的个数，前者再加上上一步求出来的块的个数（当整个图就是一个块 并且 存在入度为0的点的时候不用加），答案就是两者中的较大者。

同样的旁门左道

个人比较同意楼上的旁门左道的做法……因为一看题第一个想到的就是这种做法……我准备再对上面的方法阐释一下我的做法。

1、找到所有的入度为0的点，并沿着它遍历标记，记录个数。inc(ans1); 2、对于剩下的点找有几个块，记录个数。inc(ans1); 3、找到所有出度为0的点，记录个数。inc(ans2);

第一问结果:ans1; 第二问结果： max(ans1,ans2) (ans2>0) ans1-1 (ans2=0)

可能有考虑不周的情况……但是就那么一下子Cheat过了……如果有敬请大牛们指出！

{BY Skywalker_Q}

先拓扑排序

看到有人第一问对无向图染色。 感觉可以，先拓扑排序一下（虽然原图不一定是DAG）。然后仍然按有向图染色。求色数。这个更好理解。 见C++代码 --liuzhao2

参考代码

C

C++

Pascal