P5633 最小度限制生成树

### [P5633 最小度限制生成树](https://www.luogu.com.cn/problem/P5633) 不妨设 $s = 1$。 **问题描述**：给定 $k$，求点 $1$ 的度数为 $k$ 的最小生成树。 该问题有 $\mathcal{O}(m\log V\alpha (m))$ 的 WQS 二分做法，不在本文讨论范围内，感兴趣的同学可自行查阅资料。 先求出不含点 $1$ 的最小生成森林 $T$，则不在森林上的边一定无用。 > **证明**：设 $e = (u, v, w)$ 为非树边，根据最小生成树的基本性质，存在连接 $u, v$ 的树边构成的路径 $P$，且路径上每条边的权值不大于 $w$。 > > 假设 $e$ 在最小 $k$ 度生成树上，断开 $e$，$u, v$ 不连通。因此 $P$ 上存在一条边使得其两侧不连通，加入该树边即可。$\square$ 设 $2\sim n$ 每个点的点权为它和 $1$ 之间的边权，若不存在则为 $+\infty$。考虑最终生成树，将 $1$ 删去后整张图裂成 $k$ 个连通块，每个连通块会选择与 $1$ 相连的权值最小的边，即点权最小值。故一棵最小生成树可理解为：从 $T$ 删去若干条边，使图分裂为 $k$ 个连通块。在每个连通块中选择权值最小的点与 $1$ 相连。这样，可以用只含 $2\sim n$ 的森林描述最小 $k$ 度生成树。 $T$ 初始的连通块数量决定了度数的下界，而点权不为无穷大的点的数量决定了度数的上界。为方便讨论，以下设 **$T$ 连通且 $1$ 和每个点均有边**，则最小 $1\sim n - 1$ 度生成树均存在。 最小生成树可以贪心，那么最小 $k$ 度生成树是否也可以贪心呢？能否每次贪心地删去一条树边，使得 $w(T') - w(T)$ 最小？ 考虑删去树边 $e$ 后树的权值如何变化：设删去 $e$ 前 $e$ 所在连通块为 $C$，最小权点为 $x$。删去 $e$ 后 $C$ 分裂为两个连通块 $C_1, C_2$，不妨设 $x$ 是 $C_1$ 的最小权点，同时设 $C_2$ 的最小权点为 $y$，则权值变化量为 $f(e) = w(T') - w(T) = w(y) - w(e)$。 > **结论**：对于初始最小生成树 $T$，考虑使得 $f(e)$ 最小的边 $e$。对于任意 $2\leq k < n$，存在最小 $k$ 度生成树 $T_k$ 删去了 $e$。 > > **证明**：设 $x, y$ 分别为删去 $e$ 后两个连通块 $C_1, C_2$ 的最小权点，其中有一个是 $T$ 的最小权点，设为 $x$，则 $x$ 在任何连通块内都是最小权点，所以 $x$ 一定被选中。 > > 根据 $f(e)$ 的最小性，$e$ 一定是 $T$ 的连接 $x, y$ 的路径 $P$（$P = p_0(x)\to p_1 \to \cdots \to p_c(y)$）上的最大权边。 > > 假设 $e\in T_k$ 并从 $T_k$ 中删去点 $1$，设包含 $e$ 的连通块为 $C$。 > > - 若 $y$ 被选中：因为 $x, y$ 均被选中，所以它们在 $T_k$ 上不连通。设 $P$ 和 $C$ 的交集为路径 $Q$。因为 $e\in Q$，所以 $Q$ 非空，设为 $p_l\rightsquigarrow p_r$（$0\leq l < r\leq c$）。 > > - 若 $C$ 被选中的点在 $e$ 左侧（含有 $x$ 一侧的子树），则 $y\notin C$（因为 $y$ 也被选中），即 $r < c$。加入边 $(p_r, p_{r + 1})$，删去 $e$，考虑权值变化： > > - 因为 $e$ 是 $P$ 的最大权边，所以 $w(e) \geq w(p_r, p_{r + 1})$。 > - 因为 $C$ 被选中的点不变，其它连通块没有缩小，所以被选中的点的权值之和不增。 > > 这说明调整后权值不增。 > > - 若 $C$ 被选中的点在 $e$ 右侧（含有 $y$ 一侧的子树），则 $x\notin C$，即 $0 < l$。加入边 $(p_{l - 1}, p_l)$，删去 $e$，类似可证权值不增。 > > - 若 $y$ 未被选中：因为 $y$ 是 $e$ 右侧的最小权点，所以 $y$ 所在连通块一定包含 $e$ 左侧的点，因此 $y\in C$。设任意一条与 $x$ 所在连通块 $C_x$ 相连的被删去的边为 $e'$（因为 $k\geq 2$，所以 $e'$ 存在），它连接的另一个连通块 $C'$ 的最小权点为 $y'$。在原树 $T$ 中删去 $e$ 后，另一个连通块 $C''$ 包含 $C'$，所以 $C''$ 的最小点权不大于 $w(y')$，因此 $f(e') \leq w(y') - w(e')$。 > > 加入边 $e'$，对权值的影响为 $w(e') - w(y')$。然后删去 $e$。因为 $C$ 的最小权点在 $y$ 左边，所以 $C$ 分裂出的两个连通块 $C_1, C_2$，一个的最小权点为 $C$ 最小权点，另一个包含 $y$，最小点权不大于 $w(y)$，对权值的影响不大于 $w(y) - w(e) = f(e)$。而 $f(e) \leq f(e') \leq w(y') - w(e')$，因此权值不增。 > > 综上，总可以调整使得 $T_k$ 权值不增且 $e\notin T_k$。$\square$ 因此，在求最小 $2\leq k < n$ 度生成树之前，可直接将 $f(e)$ 最小的 $e$ 删去。注意到删去后两个子树的贡献独立，结合上述结论，我们猜测每个点的贡献都是独立的。 设 $f_k(T)$（$1\leq k\leq |T|$）表示当初始树为 $T$ 时（不含点 $1$），它的最小 $k$ 度生成树的权值。设 $T_k$ 表示对应连通块形态（不含点 $1$）。即从 $T$ 删去 $k - 1$ 条边，使其裂成 $k$ 个连通块，所有边权加上每个连通块最小点权的最小值，以及取到最小值时的形态。 > **结论**：对于 $2\leq k \leq |T|$ 和任意 $T_{k - 1}$，存在 $T_k$ 为 $T_{k - 1}$ 删去一条边，且 $f_{k}(T)$ 关于 $k$ 在 $[1, |T|]$ 上下凸。 > > **证明**：当 $|T| = 1$ 或 $2$ 时显然成立。 > > 若 $|T| > 2$，根据上述结论，设使得删去后新的权值最小的边为 $e$（不一定是权值最小的边），可钦定 $T_{2\sim |T|}$ 一定删去 $e$。 > > 设删去 $e$ 后得到的两棵树为 $T'$ 和 $T''$，归纳假设 $T'$ 和 $T''$ 满足结论。 > > 因为 $T$ 和 $T''$ 的贡献独立，所以 $f_k(T)$ 等于 $f_{k_1}(T') + f_{k_2}(T'')$ 的最小值，其中 $1\leq k_1 \leq |T'|$，$1\leq k_2\leq |T''|$，且 $k_1 + k_2 = k$。这是下凸函数的 $\min +$ 卷积，根据经典理论（闵可夫斯基和），$f_k$ 也是下凸的。而 $f_{k_1}(T')$ 和 $f_{k_2}(T'')$ 的每个差分值都对应 “删去一条边产生的贡献”，所以 $f_k(T)$ 的每个差分值都对应 “从 $T'$ 或 $T''$ 中删去一条边产生的贡献”。 > > 另一种理解方式：结论实际上说明了在 $T_1\to T_2\to \cdots \to T_{|T|}$ 的过程中，每次删去一条使得新的权值最小的边，且权值变化量（每条边的代价）随着删边而不降（下凸即二阶导非负，$f_{k + 1}(T) - f_{k}(T)\geq f_k(T) - f_{k - 1}(T)$）。现在 $T$ 分裂成 $T'$ 和 $T''$，因为 $T'$ 和 $T''$ 独立，所以删去使得新的权值最小的边相当于初始令 $k_1, k_2 = 1$，每次选择 $f_{k_1 + 1}(T') - f_{k_1}(T')$ 和 $f_{k_2 + 1}(T'') - f_{k_2} (T'')$ 较大的那个差分值，令其为 $f_{k + 1}(T) - f_k(T)$，然后将 $k$ 和被选中的 $k_i$ 加上 $1$。 > > 此时只需证明 $f_2(T) - f_1(T) = f(e)\leq f_3(T) - f_2(T)$。 > > 可以证明在子图上删去一条边的代价不小于在原图上删去这条边的代价：设在原图删去 $e'$ 之后，不含 $x$ 的连通块为 $C$，新增点权为 $C$ 的最小点权 $w(C)$。在子图删去 $e'$ 之后，一定有一侧连通块 $C'$ 包含于 $C$。新增点权为两侧连通块最小点权的较大值，不小于 $C'$ 的最小点权 $w(C')$。而 $C'\subseteq C$，所以 $w(C) \leq w(C')$。 > > 结合 $f(e)$ 的最小性，得证。$\square$ 上述结论告诉我们，随着 $k$ 增大，已经删去的边不会再出现，已经加入的点不会再消失。 至此，存在 $n ^ 2$ DP 做法：对每个连通块以最小权点为根 DFS，求出每个子树的最小点权，可知删去每条边的权值变化量。取代价最小的边删去即可。 若删去 $e$ 后新增点 $y$，则称 $e$ 被 $y$ 删去。根据结论，每条边被固定的点删去。考虑求出 $e$ 被哪个点删去。 设删去 $e$ 之前所在连通块的最小权点为 $x$，则 $e$ 在 $x, y$ 的路径上，且 $e$ 是路径边权最大值（对边权相同的边任意钦定大小关系，不影响答案）。设 $C$ 为包含 $e$ 的权值不大于 $w(e)$ 的边形成的连通块，考察 $C$ 的状态。 注意到对于 $x', y'$ 至少一个不属于 $C$ 的操作，$C$ 中不可能有边被删掉，因为 $x', y'$ 之间的路径如果经过 $C$，那么一定经过权值大于 $w(e)$ 的边（由 $C$ 的定义可知）。这说明当 $C$ 的第一条边被删去时，一定有 $x', y'\in C$ 且 $x' = x$。 设 $C_x$ 为 $e$ 的 $x$ 一侧与 $C$ 的交，另一侧为 $C_y$。设 $y_{\min}$ 为 $C_y$ 的最小权点。设 $x', y'$ 删去的边为 $e'$。 - 如果 $y'\in C_y$，则 $x', y'$ 路径上的最大权边为 $e$，得 $e' = e$，推出 $y' = y_{\min}$。 - 如果 $y'\in C_x$，则 $w(e') < w(e)$（$e$ 是 $C$ 的最大边权），根据 $w(y') - w(e')$ 的最小性得 $w(y') < w(y_{\min})$。新的 $x$ 有可能变为 $y'$，但无论何种情况点权均不大于 $y_{\min}$。 因此 $y = y_{\min}$，即 $e$ 一定被 $y_{\min}$ 删去。 在 Kruskal 的过程中维护连通块的最小点权。用 $e$ 合并两个连通块时，可求出删去 $e$ 产生的贡献 $c(e)$ 等于最小点权的较大值减去 $w(e)$。将 $e$ 按 $c(e)$ 从小到大排序得 $e_{1\sim n - 1}$，则 $f_{k + 1}(T) = f_{k}(T) + c(e_k)$。 最后处理遗留的细节：之前钦定了 $T$ 连通且 $1$ 与 $2\sim n$ 每个点相连。对于 $T$ 不连通的情况是一样的，因为 $T$ 的每个连通块独立，连通块数决定了最小的 $k$，对小于 $k_{\min}$ 的 $k$ 无解。如果权值为正无穷，说明 $k$ 超过上界（上界为初始连通块数，加上 $c$ 值不为正无穷的边数），同样无解。 算法在 $\mathcal{O}(m\log m)$ 的时间复杂度内，对每个 $1\leq k \leq n - 1$ 判定最小 $k$ 度生成树是否存在，若存在则可以求出其权值。 ```cpp #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdi = pair<double, int>; using ull = unsigned long long; #define ppc(x) __builtin_popcount(x) #define clz(x) __builtin_clz(x) bool Mbe; // mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnd(1064); int rd(int l, int r) {return rnd() % (r - l + 1) + l;} constexpr int mod = 1e9 + 7; void addt(int &x, int y) {x += y, x >= mod && (x -= mod);} int add(int x, int y) {return x += y, x >= mod && (x -= mod), x;} int ksm(int a, int b) { int s = 1; while(b) { if(b & 1) s = 1ll * s * a % mod; a = 1ll * a * a % mod, b >>= 1; } return s; } constexpr int Z = 1e6 + 5; int fc[Z], ifc[Z]; int bin(int n, int m) { if(n < m) return 0; return 1ll * fc[n] * ifc[m] % mod * ifc[n - m] % mod; } void init_fac(int Z) { for(int i = fc[0] = 1; i < Z; i++) fc[i] = 1ll * fc[i - 1] * i % mod; ifc[Z - 1] = ksm(fc[Z - 1], mod - 2); for(int i = Z - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod; } char buf[1 << 20], *p1 = buf, *p2 = buf; #define getc() (p1 == p2 && (p2 = (p1 = buf) + \ fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++) inline int read() { int x = 0; char s = getc(); while(!isdigit(s)) s = getc(); while(isdigit(s)) x = x * 10 + s - '0', s = getc(); return x; } // ---------- templates above ---------- constexpr int N = 5e5 + 5; int n, m, s, k, val[N], fa[N]; int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);} struct edge { int u, v, w; bool operator < (const edge &z) const { return w < z.w; } } e[N]; void mian() { cin >> n >> m >> s >> k; memset(val, 0x3f, N << 2); int cnt = 0, ans = 0; for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; if(u == s) val[v] = min(val[v], w); else if(v == s) val[u] = min(val[u], w); else e[++cnt] = {u, v, w}; } sort(e + 1, e + cnt + 1); for(int i = 1; i <= n; i++) fa[i] = i; vector<int> dt; for(int i = 1; i <= cnt; i++) { int u = find(e[i].u); int v = find(e[i].v); if(u == v) continue; if(val[u] > val[v]) swap(u, v); fa[v] = u, ans += e[i].w; if(val[v] < 1e9) dt.push_back(val[v] - e[i].w); } int deg = 0; for(int i = 1; i <= n; i++) { if(fa[i] != i || i == s) continue; if(val[i] > 1e9) cout << "Impossible\n", exit(0); deg++, ans += val[i]; } if(deg > k || deg + dt.size() < k) cout << "Impossible\n", exit(0); sort(dt.begin(), dt.end()); for(int i = 0; i < k - deg; i++) ans += dt[i]; cout << ans << "\n"; } bool Med; int main() { fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0); ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); #ifdef ALEX_WEI FILE* IN = freopen("1.in", "r", stdin); FILE* OUT = freopen("1.out", "w", stdout); #endif int T = 1; while(T--) mian(); fprintf(stderr, "%d ms\n", int(1e3 * clock() / CLOCKS_PER_SEC)); return 0; } /* g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI */ ```