图论好题感悟

· · 个人记录

前言：好题不是指难度很大，而是指思路巧妙，所以推荐的题难度偏低。

Problem 1

P4826

改掉做题看标签的习惯！！！

这道题考察我们观察值域的能力，发现这道题1≤N≤2000,所以索性每两个的点都建一条边权为两点xor值的边，最后跑最大生成树即可。

想到这题和生成树有关还可以从别的角度出发。每个队伍肯定是都要参赛，因为要让得分最大，但打一场比赛后，一定有一个队伍淘汰，所以一定会打n-1场比赛，不难想到这其实是n个顶点，n-1条边。 还有一定要开long long......

Problem 2

P7192

最短路

---图论中创意十分多，考察十分多的算法。

这道题其实也是结果不难，但创意十足，实际上就是处理边权做了改动。我们提前处理出T先生到某个十字路口的时间，接着在dijkstra中，将Luka到该十字路口的时间和T老师的时间做比较在计算边权即可。巧妙的解决了道路被封锁的问题，时间复杂度不劣，因为我们只在一开始花O(g)的复杂度预处理出了T老师的时间。

Problem 3

P11860

又是最短路。极其聪明的思路把边看作点。

由于本题的所谓“边权”只和两边的边权差有关，所以把边看成点是十分不错的思路。

兴致勃勃的把每个点的出边之间都建了一条边，我们发现只是建边复杂度是到O( {\textstyle \sum_{i=1}^{n} d_i^2} )了，这显然不行，若是菊花图是包炸的。

优化建边，我们可以对边进行排序，只建相邻的两边，这样从一条边去另一条边可以按边权的顺序一步一步爬上去，这样的总价值和直接去是一样的。（w_{i + 1}-w_i+w_{i+2}-w_{i+1}......+w_{j-1}-w_{j-2}-w_j-w_{j-1}）

注意数组的初始值！！！

Problem 4

P9484

题意十分简单，只有i,j是倍数关系的时候才有一条边权为i-j的无向边，询问x到y 的最短路。

一种是2*gcd-x-y，另一种是2*lcm-x-y,显然前者更优。 最阴的是用cin,cout会TLE，要用scanf,printf。