2017-team2/graph

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

最近遇到了几个感觉有相似特点的图论题，大多都是算法复杂度本身比较高的图论题，用边和点的关系加以限制成稀疏图，比如n-1<=m<=n+100诸如此类，也有遇到在转化为图论模型前人为将数据规模降低的题，感觉中国赛区很喜欢这类风格的题目，就来把这几题整理一下（虽然里面也有几题不完全符合这个分类）：

题目：[[BR]][[BR]]
1.NEERC 2015：判断图是否存在汉密尔顿回路并且输出回路，2<=n<=10^5^, m<=n+20.

2.Sichuan Provincial 2017：求图的生成树个数，1<=n<=10^5^, n<m<n+100.

3.Sichuan Provincial 2016：多组询问求两点最短路，1<=n<=10^5^,0<m-n<100,1<=q<=10^5^

4.2016 - CCPC - Hangzhou：将编号为s+1到s+n的人放到1到n的编号座位里，要求每个人的座位编号是人的编号的因子，n,s<=10^9^

5.2014 - ICPC - Asia - Tokyo：询问哪些边一定是在最小生成树上的，3<=n<=500,n-1<=m<=min(50000,n(n-1)/2)

解法：[[BR]][[BR]]
1.因为汉密尔顿回路需要n条边，所以如果某个点有太多的出边就会爆炸，所以加以限制后搜索哪个点取哪条边加一些剪枝即可。[[BR]][[BR]]
2.首先把叶子删掉,把二度点收缩,就会剩下一个 200 个点的图。这个图中的边,可能是原来的 k 条边。那么选它有 1 种方案,不选它有 k 种方案。需要改造一下 Matrix Tree 定理来数。 [[BR]][[BR]]
3.先建一棵生成树，然后对于不在生成树的100条边的200个点向全图跑bfs求出到每个点的最短路径，对于询问x,y,要不就是直接在生成树上走，要不就是经过200个点中的某一个，枚举一下经过哪个，用d[x][i]+d[y][i]和树上距离全部取min即可。此外另一种做法是先把1度点删掉，2度点缩起来，这样会剩下200个关键点，floyd把这200个点之间的最短路求出来，那么两个点的最短路大致就是走到最近的关键点，然后走关键点之间的最短路。[[BR]][[BR]]
4.显然如果n比较小，这是个经典的二分图模型，所以考虑如何缩减数据范围，对于编号x，如果能放在编号x的座位显然是最优的，这样就把重复的部分去掉了，另外对于两个质数，他们只能放在1，就会出现矛盾，所以当n大于相邻素数间隔的时候必然不存在方案，所以设一个比较科学的阙值(比如800)，小于的话直接二分图判定就好。[[BR]][[BR]]
5.先建一棵最小生成树，对于每一条非树边(x,y,w)，将x到y在树上的边拿出来，其中所有边权为w的边都是可以被替换的。

心得：[[BR]][[BR]]
1.对于1、2、3三题，很明显是三个经典问题，而且并没在定义上有附加条件，但是数据范围比正常解法要大，一般来说可以果断判定是没有什么别的巧妙方法的(有的话这个经典模型的算法就会变了)，所以直接考虑如何将数据规模缩减就好，三道题对于边的下限都是有硬性要求的(汉密尔顿回路有n条边，生成树有n-1条边，保证联通要n-1条边)，所以考虑如何在满足定义的情况下直接考虑“多余部分”对答案的贡献，而且一般来说最后的整体解法和正常数据的解法是一样的(该搜索还是搜索，该跑matrix还是matrix)，至于第三题，其第二种做法(叉姐提供的)其实也是一样的，通过把读数为1的点删掉，度数为2的点缩起来后跑floyd，和2的预处理方法一模一样。而本人的做法，实际上就是考虑答案是否与“多余部分”有关系，分类处理一下就好。[[BR]][[BR]]
2.如果感觉某一个题目可以转化成经典图论模型但是数据范围过大的时候，可以给自己一些时间去思考是否能够通过贪心或者预处理把数据规模降下来，而且一般来说总会存在一个阙值，在大于阙值的时候直接能得到答案，小于的时候能够转成经典模型来做(这也提示我们可以通过原本算法的使用数据范围去猜测这个结论)，如4中通过贪心及简单的数学常识就将原问题化为数据规模非常小的问题从而通过经典图论模型去解决。[[BR]][[BR]]
3.对于一类图论中的判定或者计数问题，可以先把一组基本情况找出来，然后看看“多余部分”是否能够起到替代或者优化的作用，这部分往往可以直接暴力求解。[[BR]][[BR]]
4.对于“多余部分”，一般来说可以考虑把这一小部分进行彻底处理，即使比较暴力也无所谓，比如3直接就处理了“多余部分”每一个点到全图的最短路径，另一种就是考虑如何利用“多余部分”把无用的数据部分给去掉，比如2里将度数为1、2的点缩掉就会变得很能做了，要不就拿来剪枝吧.....
5.似乎把度数为1的点删了，度数为2的点缩了，一般都能很方便地转化为我们需要的数据规模呢，比如2和3，但有时候不一定需要就是了，比如3.

最近遇到了几个感觉有相似特点的图论题，大多都是算法复杂度本身比较高的图论题，用边和点的关系加以限制成稀疏图，比如n-1<=m<=n+100诸如此类，也有遇到在转化为图论模型前人为将数据规模降低的题，感觉中国赛区很喜欢这类风格的题目，就来把这几题整理一下（虽然里面也有几题不完全符合这个分类）：

题目：

1.NEERC 2015：判断图是否存在汉密尔顿回路并且输出回路，2<=n<=10⁵, m<=n+20.

2.Sichuan Provincial 2017：求图的生成树个数，1<=n<=10⁵, n

3.Sichuan Provincial 2016：多组询问求两点最短路，1<=n<=10⁵,05

4.2016 - CCPC - Hangzhou：将编号为s+1到s+n的人放到1到n的编号座位里，要求每个人的座位编号是人的编号的因子，n,s<=10⁹

5.2014 - ICPC - Asia - Tokyo：询问哪些边一定是在最小生成树上的，3<=n<=500,n-1<=m<=min(50000,n(n-1)/2)

解法：

1.因为汉密尔顿回路需要n条边，所以如果某个点有太多的出边就会爆炸，所以加以限制后搜索哪个点取哪条边加一些剪枝即可。

2.首先把叶子删掉,把二度点收缩,就会剩下一个 200 个点的图。这个图中的边,可能是原来的 k 条边。那么选它有 1 种方案,不选它有 k 种方案。需要改造一下 Matrix Tree 定理来数。

3.先建一棵生成树，然后对于不在生成树的100条边的200个点向全图跑bfs求出到每个点的最短路径，对于询问x,y,要不就是直接在生成树上走，要不就是经过200个点中的某一个，枚举一下经过哪个，用d[x][i]+d[y][i]和树上距离全部取min即可。此外另一种做法是先把1度点删掉，2度点缩起来，这样会剩下200个关键点，floyd把这200个点之间的最短路求出来，那么两个点的最短路大致就是走到最近的关键点，然后走关键点之间的最短路。

4.显然如果n比较小，这是个经典的二分图模型，所以考虑如何缩减数据范围，对于编号x，如果能放在编号x的座位显然是最优的，这样就把重复的部分去掉了，另外对于两个质数，他们只能放在1，就会出现矛盾，所以当n大于相邻素数间隔的时候必然不存在方案，所以设一个比较科学的阙值(比如800)，小于的话直接二分图判定就好。

5.先建一棵最小生成树，对于每一条非树边(x,y,w)，将x到y在树上的边拿出来，其中所有边权为w的边都是可以被替换的。

心得：

1.对于1、2、3三题，很明显是三个经典问题，而且并没在定义上有附加条件，但是数据范围比正常解法要大，一般来说可以果断判定是没有什么别的巧妙方法的(有的话这个经典模型的算法就会变了)，所以直接考虑如何将数据规模缩减就好，三道题对于边的下限都是有硬性要求的(汉密尔顿回路有n条边，生成树有n-1条边，保证联通要n-1条边)，所以考虑如何在满足定义的情况下直接考虑“多余部分”对答案的贡献，而且一般来说最后的整体解法和正常数据的解法是一样的(该搜索还是搜索，该跑matrix还是matrix)，至于第三题，其第二种做法(叉姐提供的)其实也是一样的，通过把读数为1的点删掉，度数为2的点缩起来后跑floyd，和2的预处理方法一模一样。而本人的做法，实际上就是考虑答案是否与“多余部分”有关系，分类处理一下就好。

2.如果感觉某一个题目可以转化成经典图论模型但是数据范围过大的时候，可以给自己一些时间去思考是否能够通过贪心或者预处理把数据规模降下来，而且一般来说总会存在一个阙值，在大于阙值的时候直接能得到答案，小于的时候能够转成经典模型来做(这也提示我们可以通过原本算法的使用数据范围去猜测这个结论)，如4中通过贪心及简单的数学常识就将原问题化为数据规模非常小的问题从而通过经典图论模型去解决。

3.对于一类图论中的判定或者计数问题，可以先把一组基本情况找出来，然后看看“多余部分”是否能够起到替代或者优化的作用，这部分往往可以直接暴力求解。

4.对于“多余部分”，一般来说可以考虑把这一小部分进行彻底处理，即使比较暴力也无所谓，比如3直接就处理了“多余部分”每一个点到全图的最短路径，另一种就是考虑如何利用“多余部分”把无用的数据部分给去掉，比如2里将度数为1、2的点缩掉就会变得很能做了，要不就拿来剪枝吧.....

5.似乎把度数为1的点删了，度数为2的点缩了，一般都能很方便地转化为我们需要的数据规模呢，比如2和3，但有时候不一定需要就是了，比如3.