题意
给定一张 n n n 个点 m + k m+k m+k 条边的无向图,点有点权 p x p_x px,边有边权 c ( u , v ) c(u,v) c(u,v)。在原图的最小生成树中,对于一条边 ( u , v ) (u,v) (u,v),它产生的贡献为 c ( u , v ) × p x c(u,v)\times p_x c(u,v)×px,其中的点 x x x 在树上到 1 1 1 的路径中必须含有 ( u , v ) (u,v) (u,v) 这条边。
你可以自定义其中指定的 k k k 条边的边权,使得这些边产生的贡献最大,求这些边的贡献之和。如果边不在最小生成树中则贡献为 0 0 0。
k ≤ 20 , n ≤ 1 0 5 , m ≤ 3 × 1 0 5 k\le20,n\le10^5,m\le3\times10^5 k≤20,n≤105,m≤3×105。保证边权互不相同。
解法
k k k 只有 20 20 20,所以我们可以 O ( 2 k ) O(2^k) O(2k) 枚举 k k k 中的哪几条边最终被放进了最小生成树中,然后算出这几条边边权最多可以取多少,使得这些边全部都在树中。其他自定义的边我们可以将它们的权值设为 + ∞ +\infty +∞,不做考虑。
设当前枚举到的边集为 K ′ K' K′,已经给定边权的边集为 M M M,待定边权的边集为 K K K。想让最小生成树中一定包含 K ′ K' K′,可以在算最小生成树时将 K ′ K' K′ 中的边提前加入树中(也需要保持树结构),然后才按照边权大小考虑 M M M 中的边。
对于 K ′ K' K′ 中边的边权上界,可以利用一个最小生成树的性质:对于一条非树边 ( u , v ) (u,v) (u,v),那么如果将其加入树中一定会形成环,而环上树边的权值都小于等于 c ( u , v ) c(u,v) c(u,v),否则 ( u , v ) (u,v) (u,v) 就会变成树边。所以在算完生成树后,枚举 M M M 中每条非树边 ( u , v ) (u,v) (u,v), u → l c a u\to lca u→lca 和 v → l c a v\to lca v→lca 两条链上属于 K ′ K' K′ 的边的边权都必须小于等于 c ( u , v ) c(u,v) c(u,v)。
计算贡献就以 1 1 1 为根遍历整棵最小生成树即可,具体见实现。但这样复杂度为 O ( 2 k m + m log m ) O(2^km+m\log m) O(2km+mlogm)(提前排好序),瓶颈在于每次都必须把 M M M 中的边全部考虑完。
设想一下,如果把 K K K 中的边全提前加入树中,此时树上属于 M M M 的边最少,那么这些属于 M M M 的边(边集记为 M ′ M' M′),不论你怎么选 K ′ K' K′, M ′ M' M′ 中的边一定都会在最小生成树上。其他情况下,如果 M ′ M' M′ 中的某几条边不在最小生成树上,那么说明有更优的 M M M 中的边可以替代,那么这些更优的边就会在 M ′ M' M′ 中替代这几条边。
所以我们可以先算出 M ′ M' M′,因为边权互不相同,所以 M ′ M' M′ 是确定的。对于其中边组成的一个连通块,即使选择不一样的 K ′ K' K′,最小生成树中这个连通块的部分选择的边就是不变的。所以我们就可以把这么多个连通块缩成一个点,每次跑最小生成树就不再需要考虑这个点的内部边的情况了。
M ′ M' M′ 可以认为是将 K K K 全放进最小生成树中,算完整棵树后再把 K K K 全部删掉后剩下的边,所以一共有 K + 1 K+1 K+1 个连通块。我们在删除 K K K 后对 M M M 中的边继续跑最小生成树,把树构建完整。此时新加的连接着两个不同连通块的 k k k 条边(相当于替代了原来 K K K 中边的作用),就可以和每轮枚举的 K ′ K' K′ 中的边组成最终的最小生成树了。
于是,每轮最小生成树还需要考虑的边就只剩下了 2 k 2k 2k 条。
实现
首先第一遍 Kruskal
跑出 M ′ M' M′,开两个并查集 F , G F,G F,G,缩点也可以利用并查集 G G G,在加完 K K K 中的边后再加的边就是组成连通块的边,对于这些边在合并完 F F F 后另外再把 G G G 也合并了。由于我们只关心 K ′ K' K′ 中边的贡献,所以每个连通块内部的边的贡献是不重要的,只需要记录连通块内点的点权之和。
缩完点后,用并查集 G G G 继续跑 Kruskal
,记录这一轮 Kruskal
新加的边(边两端的点都代表一个连通块,记为 n e w E newE newE),然后就可以开始枚举 K ′ K' K′ 了。我们用一个 S S S 表示当前 K ′ K' K′ 的选择,如果 S S S 二进制第 i i i 位为 1 1 1 则说明 K K K 中第 i i i 条边被选进 K ′ K' K′。
也是先将 K ′ K' K′ 提前加入树中,再将 n e w E newE newE 中的边加入树中,并记录这些边是否是树边。我们将 ( u , v ) (u,v) (u,v) 这条边的贡献记录在 u , v u,v u,v 中深度更深的点上。在树上跑 dfs
算出每个点的深度和子树中点的点权之和,然后枚举 n e w E newE newE 中的非树边,把 u → l c a u\to lca u→lca 和 v → l c a v\to lca v→lca 上点所代表的边的上界进行更新。由于 k k k 不大所以可以暴力跳祖先。
对于点 u u u,我们令子树点权之和为 s i z u siz_u sizu, u u u 连接其父亲的这条边边权上界为 m x u mx_u mxu。然后对于每条 K ′ K' K′ 中的边 ( u , v ) (u,v) (u,v),这条边对本轮答案产生的贡献即为 u , v u,v u,v 中深度较大的点的 s i z siz siz 与 m x mx mx 之积。
代码
// 先将k条边全部加入后跑最小生成树
// 去掉k条边后缩点
// 然后就可以2^k跑
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5, maxm = 1e6 + 5;
const int maxk = 50;
struct Edge { int w,u,v; } E[maxm],K[maxn];
int n,m,k;
int F[maxn], G[maxn];
int find(int u, bool op = true) {
if (op) return u == F[u] ? u : F[u] = find(F[u], true);
else return u == G[u] ? u : G[u] = find(G[u], false);
}
void unite(int u, int v, bool op = true) {
if (op) F[u] = v;
else G[u] = v;
}
void Kruskal1() {
for (int i = 1;i <= n;i ++) F[i] = G[i] = i;
for (int i = 1,u,v;i <= k;i ++) {
u = find(K[i].u), v = find(K[i].v);
if (u != v) unite(u,v);
}
sort(E + 1,E + m + 1,[&](const Edge &x,const Edge &y) { return x.w < y.w; });
for (int i = 1,u,v;i <= m;i ++) {
u = find(E[i].u), v = find(E[i].v);
if (u == v) continue;
unite(u,v);
u = find(E[i].u, false), v = find(E[i].v, false);
if (u != v) unite(u,v,false);
}
}
int tot = 0, b[maxn]; ll sum[maxk];
ll p[maxn];
void Build() {
for (int i = 1;i <= n;i ++)
if (find(i,false) == i)
sum[b[i] = ++ tot] = p[i];
for (int i = 1;i <= n;i ++) {
int f = find(i,false);
if (f == i) continue;
sum[b[i] = b[f]] += p[i];
}
}
Edge newE[maxm]; int cnt = 0;
void Kruskal2() {
for (int i = 1,u,v;i <= m;i ++) {
u = find(E[i].u,false), v = find(E[i].v,false);
if (u == v) continue;
newE[++ cnt] = Edge{E[i].w,b[E[i].u],b[E[i].v]};
unite(u,v,false);
}
}
vector<int> mp[maxk];
void addEdge(int u,int v) { mp[u].push_back(v); }
int fa[maxk],dep[maxk]; ll siz[maxk];
void dfs(int u,int f) {
dep[u] = dep[fa[u] = f] + 1;
siz[u] = sum[u];
for (auto v : mp[u]) {
if (v == f) continue;
dfs(v,u); siz[u] += siz[v];
}
}
ll mx[maxk];
void update(int u,int v,ll w) {
if (dep[u] < dep[v]) swap(u,v);
while (dep[u] > dep[v])
mx[u] = min(mx[u], w), u = fa[u];
while (u != v) {
mx[u] = min(mx[u], w);
mx[v] = min(mx[v], w);
u = fa[u], v = fa[v];
}
}
bool vis[maxk];
void Kruskal(int s) {
memset(vis,false,sizeof(vis));
for (int i = 1;i <= tot;i ++){
F[i] = i;
mp[i].clear();
}
for (int i = 1;i <= k;i ++)
if ((s >> (i - 1)) & 1) {
int u = find(b[K[i].u]), v = find(b[K[i].v]);
unite(u,v);
addEdge(b[K[i].u],b[K[i].v]);
addEdge(b[K[i].v],b[K[i].u]);
}
for (int i = 1;i <= cnt;i ++) {
int u = find(newE[i].u), v = find(newE[i].v);
if (u == v) continue;
unite(u,v); vis[i] = true;
addEdge(newE[i].u,newE[i].v);
addEdge(newE[i].v,newE[i].u);
}
}
ll ans = 0;
int main() {
scanf("%d%d%d",&n,&m,&k);
for (int i = 1;i <= m;i ++)
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
for (int i = 1;i <= k;i ++)
scanf("%d%d",&K[i].u,&K[i].v), K[i].w = 0;
for (int i = 1;i <= n;i ++)
scanf("%lld",&p[i]);
Kruskal1(); Build(); Kruskal2();
for (int s = 0;s < (1ll << k);s ++) {
Kruskal(s);
memset(dep,0,sizeof(dep));
memset(siz,0,sizeof(siz));
dfs(b[1],0); ll res = 0;
memset(mx,0x3f3f,sizeof(mx));
for (int i = 1;i <= cnt;i ++)
if (!vis[i]) update(newE[i].u, newE[i].v, (ll)newE[i].w);
for (int i = 1;i <= k;i ++)
if ((s >> (i - 1)) & 1) {
int u = b[K[i].u], v = b[K[i].v];
if (dep[u] < dep[v]) swap(u,v);
res += mx[u] * siz[u];
}
ans = max(ans,res);
}
printf("%lld",ans);
return 0;
}