mst

Description 有一张n个点的完全图，每个点有点权xi，边(i,j)的边权为xi xor xj 有q组询问，每次询问给出v，问将所有点权加上v对2^c-1取模之后这张图的最小生成树 n,q<20000,c<14 Solution EricHuang出的神仙题 Orz 首先n和q…

Description 给出一张n个点，m条边的图，每条边有两个边权(a,b)，求从1到n的路径中所有的权a最大值权b最大值的最小值是多少。 n<50000,m<100000 Solution 长得那么像双关键字的最小生成树。不过是最大值的和而已。那么我们可以把…

Description 最小标准差生成树。。。。 n<100,m<2000,边权<100 Solution 其实我比赛时想的是可以的，不过不用二分，而用枚举。没错，枚举平均数。不过，可能的数太多了，得另想办法。我们把排好序的数按…

Description 给出一张n个点m条边的无向联通图，点i的点权为w[i]，边(x,y)的边权为|w[x]-w[y]| q次询问，每次询问一个点对(x,y)是否存在两条不相交（边相交）的路径，如果存在，输出这两条路径上的边…

Description 给出一张n个点的完全图，第i个点的点权为pi 点(x,y)之间的边为min(px%py,py%px) 求最小生成树 n<1e5,p<1e7 Solution 先来证明一个结论：对于一个点pi，只需要向所有的kpi到(k1)pi区间中的最小值连边采用反证法&#…

Description 给出n个点,m条有权边,现对于每一条边，你需要回答出包含这条边的最小生成树的总边权值。 n,m<2*10^5 Solution 题解和题意一样简洁系列。首先求出mst，然后对于每一条不在mst里面的边，相当于把它和mst中的一条边替换。若…