图论好题感悟

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

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

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

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

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

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

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

兴致勃勃的把每个点的出边之间都建了一条边，我们发现只是建边复杂度是到$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}）$

注意数组的初始值！！！

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

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