小衣同学的博客

其中x[now]是临界位置，q[i]是询问的值，q[i]严格大于x[now]，且严格小于x[now+1]有个没弄懂的地方，是中点只能是(e[i].w+e[j].w+1)/2，也就是向上取整。那么x固定时，每一条边都是对应有(k∈(-1,1),b)的一个贡献，线性相加即可。那么由于q[i]>x[now]，所以当x[now]处，生成树有多个时，考虑大于的值的贡献是w-x[now]，小于的贡献是x[now]-w，q(q<=1e7)次询问，每次给定一个整数x(x<=1e8)，对其暴力做最小生成树求权值即可，

1. 最大化最小值，首先考虑二分，二分答案v，将(a[p]^a[i])

题目n(n<=1e5)个点，m(n-1<=m<=min(1e5,n*(n-1)/2)条边的无向图，不含重边和自环第i条边的权值为wi(1<=wi<=1e6)，对于每条边，判断其为最小生成树中的必要边/可行边/不可行边即，一定出现在所有MST中，可能出现在某一个MST中，不可能出现在任意一个MST中思路来源https://www.cnblogs.com/Hugh-Locke/p/9622936.html题解Kruskal求最小生成树，将相同权值的边

题目题目链接思路来源https://blog.csdn.net/qq_40400202/article/details/102461902?utm_source=app题解首先注意到，重边自环都无所谓，Kruskal并查集合并的时候，因为在同一个集合，会自然忽略掉这些从x出发，编号不大于y，考虑Kruskal重构的时候，将u和v合并(不妨u<v)，新建一个点T，点权为max(u,v)，再将u和v挂在T上，等价于直接把u挂在v上，故不用新开节点，直接建树，最后从最

题目n(n<=1e5)座山峰，第i座高度hi(hi<=1e9)，保证所有hi不同，m(m<=5e5)条边的无向图，q(q<=5e5)组询问，每次询问给出(v,x,k)，询问从点v出发，只能走不超过x(x<=1e9)的边时，从高到低第k的山峰的点号，不存在输出-1思路来源https://www.cnblogs.com/zwfymqz/p/9683523.html前置知识（Kruskal重构树）图片来自于自为风月马前卒博客，很通俗易懂了，

题目n(1<=n<=5)个和尚，每个和尚位于一个寺庙内，标号1-nm(0<=m<=1e3)个其他地方，标号n+1到n+m以下n+m个数，为在第i个地方打井所需的代价以下p(0<=p<=5e3)行，每行u，v，w，为在标号u和标号v之间建边的代价w求最小代价和，使得所有和尚都能喝到水思路来源https://blog.csdn.net/u...

题目N(N<=200)个星球，第i个星球有pi，si两个参数pi代表星球有pi个工厂，si={0,1}代表星球是否为资源星球一个资源星球只能给一个工厂提供资源，以下m(0<m<=5e3)行u,v,w为在星球间建边的代价在工厂数<=4且资源星球数<=4的情况下最大化工厂运作数num，num相等条件下最小化建边总代价cost思路来源http...

题目n(4<=n<=50)个点，k(1<=k<=5,2*k<=n)个房子，对应k个避难所编号1到k的是房子，编号n-k+1到n的是避难所，一个房子只能对应一个避难所m(0<=m<=1e3)条已经破坏的路，u,v,w代表修缮u和v之间的道路需要花费w花费最少的代价，使得4个房子对应4个避难所思路来源https://www.cnbl...

题目n(n<=30)个点，m(m<=1e3)条边，边权w(w<=1e4)4对城市，每对城市想建立线路，代价为经过的边的边权，问最小的代价和，特别地，不同的线路经过相同的边只算一次思路来源Dup4大佬题解斯坦纳树压出每种状态j的最小值，更新ans数组的时候去掉根然后子集dp合并答案，合并答案的时候，每一对必须同时出现或不出现在一个状态里，否则转移...