2017-Sp21-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,700px)]]
== 流水账 ==
开场各自看题，yzc上机写A，'''A过'''.  cjb和sub推E，'''E过'''. cjb和sub讨论了一下F，感觉大部分都是对的只差关键的一步，cjb先上机写F，yzc和sub讨论I，很快得到了做法，yzc上机写I，'''I过'''。接下来两个小时时间，bnuoj坏掉了....sub独自推出了B，cjb想到了F的做法，上机写完了F，yzc和sub讨论好了G，上机写G，后来发现并查集不太行，cjb上机敲了个lct的板子，G也搞定了。两个小时过后，bnuoj终于能上了，连交三题，'''B过'''，F和G都wa. yzc看自己G的代码，很快发现bug，修改后提交，'''G过'''。yzc帮助cjb写了对拍，cjb发现做法有问题，打了补丁，还是不太行，最后cjb想到了正确的做法，写完获得tle，把spfa换成bfs后提交，'''F过'''。最后一个小时，yzc和sub在半猜半推做H，yzc上机写树型dp，sub在旁边调整式子，wa了一发后，最后5min '''H过'''。最后7题排在第6，Tazof也是7题排在第3，qls 8题rk1，如果没有两个小时，我们应该7题第一问题不大，但主要以适应中国题目为主，排名其次。
== 总结 ==
=== chenjb ===
emmmm差点炸在了F......来一波这种类型的图论总结吧.... [[BR]][[BR]][[BR]]
最近遇到了几个感觉有相似特点的图论题，大多都是算法复杂度本身比较高的图论题，用边和点的关系加以限制成稀疏图，比如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的点缩掉就会变得很能做了，要不就拿来剪枝吧..... [[BR]][[BR]]
5.似乎把度数为1的点删了，度数为2的点缩了，一般都能很方便地转化为我们需要的数据规模呢，比如2和3，但有时候不一定需要就是了，比如3.
=== oipotato ===
=== subconscious  ===
== 题解 ==
 [https://post.icpc-camp.org/d/576-2016-hints ICPC-CAMP]
 * D：当一个连通图是二分图的时候，显然答案是两边点数相乘，反之，显然存在一个奇环，所以任意两点路径都能通过这个环来改变奇偶，所以任意点对都满足条件。我们用并查集维护一下图的连通性及是否是二分图，直接统计答案就可以了。
 * F：跑一棵生成树出来，对于不在生成树上的100条边，上面的每一个点都在全图跑bfs预处理距离，然后对于询问，要不就直接求树上距离，要不就枚举经过那200个点的哪一个点，d[x][i]+d[y][i]求个最小值和树上距离比一比就好了。
 * J：十字链表实现大暴力就好。
== 补题 ==

流水账

开场各自看题，yzc上机写A，A过. cjb和sub推E，E过. cjb和sub讨论了一下F，感觉大部分都是对的只差关键的一步，cjb先上机写F，yzc和sub讨论I，很快得到了做法，yzc上机写I，I过。接下来两个小时时间，bnuoj坏掉了....sub独自推出了B，cjb想到了F的做法，上机写完了F，yzc和sub讨论好了G，上机写G，后来发现并查集不太行，cjb上机敲了个lct的板子，G也搞定了。两个小时过后，bnuoj终于能上了，连交三题，B过，F和G都wa. yzc看自己G的代码，很快发现bug，修改后提交，G过。yzc帮助cjb写了对拍，cjb发现做法有问题，打了补丁，还是不太行，最后cjb想到了正确的做法，写完获得tle，把spfa换成bfs后提交，F过。最后一个小时，yzc和sub在半猜半推做H，yzc上机写树型dp，sub在旁边调整式子，wa了一发后，最后5min H过。最后7题排在第6，Tazof也是7题排在第3，qls 8题rk1，如果没有两个小时，我们应该7题第一问题不大，但主要以适应中国题目为主，排名其次。

总结

chenjb

emmmm差点炸在了F......来一波这种类型的图论总结吧....

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

题目：

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

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

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

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)

解法：

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.

oipotato

subconscious

题解

ICPC-CAMP

D：当一个连通图是二分图的时候，显然答案是两边点数相乘，反之，显然存在一个奇环，所以任意两点路径都能通过这个环来改变奇偶，所以任意点对都满足条件。我们用并查集维护一下图的连通性及是否是二分图，直接统计答案就可以了。
F：跑一棵生成树出来，对于不在生成树上的100条边，上面的每一个点都在全图跑bfs预处理距离，然后对于询问，要不就直接求树上距离，要不就枚举经过那200个点的哪一个点，d[x][i]+d[y][i]求个最小值和树上距离比一比就好了。
J：十字链表实现大暴力就好。

补题

附加文件

1.png by chenjb