P5633 最小度限制生成树

Alex_Wei · 2023-07-08 14:31:42 · 题解

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 度生成树。

因此，在求最小 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 度生成树是否存在，若存在则可以求出其权值。

#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
*/