题意求 $N$ 点无向图的最小生成树，满足 $1$ 号节点度数 $\le s$ 。$N\le 30$ 。题解思想考虑构造一个以 $1$ 号节点为根的树，则 $1$ 号节点必须与子树中所有连通块相连。记录去掉 $1$ 号节点后的连通块个数，即 $1$ 号节点的最小度数，为 $tcnt$ 。（题目保证有解即 $tcnt\le s$）对每个连通块分别求出最小生成树，这样就得到了除 $1$ 号节点外...
题意一个有点权和边权的无向图，求 所有点权和为 $0$ 的子图 的最小生成树的权值和。其中点数 $N\le 16$ 。题解看了半天题才得到上面的题意，看到 $N\le 16$ ，显然是状压。用 $f[id]$ 表示当前点集状态为 $id$ 时的最优解，当 $i$ 和 $j$ 状态内的点权和为 $0$ 时，转移方程式很显然：$$f[i|j]=f[i]+\text{Kruskal}(j)$$对每...
题意有一个无向带权连通图，每条边是黑色或白色。求一棵最小权的恰好有 $need$ 条白色边的生成树。保证有解。题解我最开始想的是直接先对白边跑有 $need$ 条边的最小生成树，再对黑边跑剩下的就行了。但打到一半突然发现不行，于是便跑去看题解。显然直接跑最小生成树白边就很可能多或者少。如果多了就说明白边的权值大多比较小，那么我们就可以给所有白边加一个权值 $x$ 然后再跑；如果白边少了同理。...
题意给一个无向简单图，求最小生成树的个数，对 $31011$ 取模。其中点数 $n\le 100$ ，边数 $m\le 1000$ 。题解有个性质：在不同的最小生成树中，每种权值的边的数量一定相同。这道题又有个限制：具有相同权值的边不会超过 $10$ 条，那么就可以直接用那个性质来暴力了。先跑出来最小生成树，记录下来每种权值的边的数量 $t\_cnt[]$ 以及每种权值的起始位置 $l[]$...
这道题做法还是比较容易想到的，就是码量有点大。不严格次小生成树的思路就是先得到最小生成树，然后枚举每一条不在树里的边，找到所构成的环上权值最大的边替换掉。而这道题要求严格次小，那么权值最大的边就不能与枚举的边权值相同，如果相同就替换环上次大的边即可。我还是敲了树剖，对于最大和次大边我用pair来存，可能是STL的缘故不开O2只有90。在合并（线段树合并和lca两侧合并）时对最大和次大的处理如...
概念最小生成树即为无向图中结点构成的树中各边权值之和最小的树，可以有多种情况。一般用Kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。Kruskal算法方法可以将Kruskal算法理解成对边的贪心算法。1.将路径用邻接表存储，存储的值为起点、终点和权值；2.将邻接表按照权值为关键字排序；3.从最小权值的边开始循环，每连接起两个结点就把它们并到同一个集合（并查集实现），连接之前判断...