2020-07-08 自测赛总结
第一次自评，就被神仙 包菜了/kk
晚自习考的，大概总用时 多一点点吧。
T1
憨憨题目，虽然也写了 。
题意：有一张不保证联通的图，每一条边属于他所连接的端点中的一个。现在把每一条边划分给他所连接的端点中的一个，满足每一个端点最多给划分了一条边，且所有的边都被属于的划分方案为合法方案。求所有可能的合法方案。
读入点的数量 和边的数量 ，接下来 行每行两个整数 表示 和 之间有一条连边。
可能比较难理解吧，这里把出题人的样例解释拿出来。
：
5 4
1 2
3 2
4 5
4 5
：
6
：
共 种方案数：，，，，，
其中第 个数表示第 条连边划分给的端点。
考场得分：。
当时看了一眼题后没有仔细思考，感觉不大会，就先写了 的 。
给了另外两当分，每一个连通分量都保证全是树或环，手玩了几组数据后发现这个部分分的结论很一眼，两种情况共 ：
当连通分量是树时，由于 ，那么意味着有且仅有一个点不会划分有边，而这点是特殊点。所以考虑枚举所有的点是否是特殊点，那么这个连通分量的贡献值为树的大小即为 。
当连通分量是环是，由于 ，那么意味着所有的点都必须划分有边，没有特殊点，但是要考虑连边的方向，所以这个连通分量的贡献值为常数 。
当时想到这里感觉 稳了，而最后的 我以为会存在树套环以及环套环等乱七八糟的图的情况，就没有认真去想，拿了 分后就看第二题去了。
然后写完 的代码后过去了 ，写 的一些分数后距离考试开始过去了 ，还剩下 左右。这个时候由于想 没有什么思路，就回头继续想 ，大概没多久后就发现：一个连通分量的点数 和边数 必须满足 ，当 时即树的连通分量贡献为 ；当 时即环的连通分量或者树套环（基环树）的连通分量，贡献为 ；而当 时即为环套环的连通分量，此时必然存在有至少一个点会划分有至少 条的边，不符合题目合法方案约定，贡献为 。
代码实现：维护两个并查集，一个维护点的连通分量，一个维护边的连通分量，对于每个连通分量判断其点数 和边数 的大小关系，复杂度 ，然后就能拿到 了。
T2
题意：给定边权均为 的无向图，此时 号节点到其他节点的距离为 ，如果不连通则视为无穷大。考虑对于每次仅删去一条边后，如果对于任意的 ，都有 或者 ，那么这条边视为合法的。请按照从小到大的顺序输出合法的边。
考场得分：。
想了 ，大概还是不太会，写了个暴力：对于删去每条边跑一遍 ，一共 遍。由于所有边权均为 ，去掉优先队列，复杂度为 ，期望 。耗时 。
看了题解后发现这是一个 ** 题。由于边权为 考虑到 下去每次发现一个新的结点时，此时必定是最短距离，那么我们考虑到删去一条边后，如果这条边为非树边，那么删去他一定不会产生任何影响；否则，这个边连接的子结点如果有连边指向深度等于或者大于的非父亲结点时，这意味着删去这条边对这个子结点最短距离的要求不大于 ，符合题意。所以我们只需要对所有结点 预处理深度并建立树形图，对任意一条边判断是否非树边，然后询问子结点，所以每个点最多被询问一次，复杂度为 。
T3
一道原题，考场上没发现，也没想到标算做法：洛谷-P2573 [SCOI2012]滑雪。
有两问，第一问求能够到达的合法点，这个连边后跑一遍 统计距离大小是否为无穷，期望
第二问求到达所有合法点所需要的最小距离和，想了 分钟左右，大概考虑过一些图论的其他知识点，最后感觉有点像是网络流。花了 分钟后写完了第一问。回头一想网络流不大对，有没有什么思路，就最后大约 回头写 去了。总感觉这个模型非常熟悉，也不知道为什么居然没想到最小生成树。期望 。
考场分数：。
也不知道为什么挂成了这 ** 样。
看完 后，只觉得自己有点 ** 了，第一问是差不多的，第二问大概就是重新判下合法点的连边建一张新图，然后按照连边的目的地的高度作为第一关键字，连边的距离长度作为第二关键字，排序后跑 算法求最小生成树，就可以拿到 。原题大概是 年的 。
之所以把高度放在第一关键字，其实只是在使得能够拓展的点最多，然后再求最小生成树。
总结
图论专场
显然我对于图论的理解菜爆了，有些套路和概念不能忘记呀。
自己的预期分数虽然不高，但是总是会挂些分数，而且和同龄人之间的距离挺大的。
大概图论并不会太深入的继续学习了吧，但是 和一些暴力手法不能忘记呀。