题解 P2746 【[USACO5.3]校园网Network of Schools】

· · 题解

CAUTION！本篇目的在于纠正所有题解里的错误之处，可能有不妥之处，欢迎补充完善。

缩点。

第一问简单，求一下无入度点个数即可。

第二问简化后问题是给一张DAG求最少添加几条边使得DAG变成一个SCC。首先所有中间点（有入度有出度）肯定直接顺着走到无出度点，所以肯定是无出度点连向无入度点。

把无入度点作为点集S，把无出度点作为点集T。

二分图连边表示S点（入度为零）可以走到T点（出度为零），然后先暴力匹配，表示每一个S_i尽可能走一个互不相同的T_i点，然后所有匹配边从T_i向下一个匹配的S_{i+1}连一条边，表示从S_i\to T_i\to S_{i+1}，如此往复，最终将最后一个T_k连向开始时的S_1，此时形成一个环，是SCC。然后剩下的没被选上的是不连通的。如果是S_i点表明他所有可以走到的T都被其他S走过去了，T也是一样，能走到他的S都走到其他点T了，于是就把每一对未匹配的T向S连一下边，最后如果还剩下来就随便连了。这样，会发现左右两侧的点就都被连上了一条边。所以最少连边数量是\max(|S|,|T|)。如果要求方案的话就用这个二分图的匹配就行了，如果数据大了呢？再见

注意：上述证明结论的方法我翻阅了绝大部分网络题解，发现讲的都比较随便，都是“无出度点和无入度点随便两两匹配，直到每个点都有出度入度就是SCC了”。

错误在于：1.并不是随便选无出度点和无入度点的。hack！

n=4  m=3
1 3
1 2
4 3

2.并不是每个点都有入度和出度就是SCC了，可能是两个环通过一个有向边相连什么的。

所以我认为大部分题解的证明和构造答案方法都是错的。

当然我并没有就认为我的一定是对的。如果有谁可以推翻我的改正说法，欢迎爆踩指正。

代码什么的。。网上满天飞了。就不放了