Codeforces Gym 103446H. Life is a Game
容易注意到, 对于每一次询问, 所有经过的节点必定组成一个连通块, 而且所有经过的边必定是原图最小生成树上的包含该连通块的边集. 基于这个性质, 可以想到两种解法:
解法一
对于一个询问, 最朴素的求解办法就是按边权从小到大枚举每一条边, 如果这一条边在当前询问的连通块上, 且当前询问可以通过该边, 那么就将当前询问的连通块改为这条边所连两个连通块的并. 最后该询问的答案就是其当前连通块内所有点权值的和加上初始值. 该做法时间复杂度为 \(\mathcal O(n^2)\) .
考虑优化. 容易发现, 对于所有询问, 都必须经过的步骤是按边权从小到大枚举每一条边; 而它们的不同之处就是判定每个询问是否可以经过当前枚举的边. 又注意到在同一连通块内的所有询问的答案只和询问初始值有关, 于是可以考虑启发式合并. 对于每一个连通块, 用一个堆来维护有哪些询问在当前连通块中. 枚举边 \(e\,(u,\,v,\,w)\) 合并时先将 \(u,v\) 连通块内所有不能通过边 \(e\) 的询问处理掉, 并将它们在堆中删除后, 将剩余 \(u,v\) 所在连通块的堆按启发式合并. 每一次合并的复杂度为 \(\mathcal O(\min\{|S_u|,\,|S_v|\})\) , 因此总时间复杂度就是 \(\mathcal O(n\log n)\) .
参考代码 ( by qyw )
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=100005;
long long INF=0x3f3f3f3f3f3f3f3f;
int n,m,q,a[N];
int fa[N],sz[N];
long long rr[N],sum[N];
struct edge{int u,v,w;}e[N];
priority_queue<pii> pq[N];
bool cmp(edge a,edge b){return a.w<b.w;}
int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
void dlpq(int x,long long w)
{
while(!pq[x].empty())
{
pii u=pq[x].top();
if(-u.fi+sum[x]>=w) return;
rr[u.se]=-u.fi+sum[x],pq[x].pop();
}
}
void mgpq(int x,int y,int w)
{
while(!pq[x].empty())
{
pii u=pq[x].top();
pq[x].pop();
pq[y].push(u);
}
}
void merge(int x,int y,int w)
{
int fx=findfa(x),fy=findfa(y);
if(fx==fy) return;
dlpq(fx,w),dlpq(fy,w);
if(pq[fx].size()>pq[fy].size()) swap(fx,fy);
mgpq(fx,fy,w);
fa[fx]=fy,sum[fy]+=sum[fx];
}
void solve()
{
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i,sum[i]=a[i];
for(int i=1;i<=m;i++) merge(e[i].u,e[i].v,e[i].w);
int ff=findfa(1);
dlpq(ff,INF);
for(int i=1;i<=q;i++) printf("%d\n",rr[i]);
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
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<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
pq[x].push(pii{-y,i});
}
solve();
}
解法二
考虑按边权从小到大构造原图的 \(\text{Kruskal}\) 重构树.
每一次询问在重构树上从叶节点开始暴力跳父亲, 直到找到第一条不能通过的边 (即该边下面的子树点权值和加上初始值小于该边权值). 这样做的正确性显然, 时间复杂度为 \(\mathcal O(n^2)\) .
注意到上述暴力跳父亲的过程可以用树上倍增优化. 于是就结束了, 时间复杂度为 \(\mathcal O(n\log n)\) .
参考代码
#include <bits/stdc++.h>
using namespace std;
static constexpr int Maxn = 2e5 + 5, LOG = 19;
static constexpr int64_t inf = 0x3f3f3f3f3f3f3f3f;
int n, m, q, nc;
int64_t a[Maxn];
struct Edge {
int u, v;
int64_t w;
Edge() = default;
Edge(int u, int v, int64_t w) : u(u), v(v), w(w) { }
friend bool operator < (const Edge &lhs, const Edge &rhs) {
return lhs.w < rhs.w;
}
} e[Maxn];
int fa[Maxn];
int fnd(int x) {
return fa[x] == x ? x : fa[x] = fnd(fa[x]);
} // fnd
vector<int> g[Maxn];
int64_t b[Maxn], sa[Maxn];
int64_t c[LOG][Maxn];
int par[LOG][Maxn];
void dfs(int u, int fa) {
sa[u] = (u > n ? 0 : a[u]); par[0][u] = fa;
for (int j = 1; j < LOG; ++j) par[j][u] = par[j - 1][par[j - 1][u]];
for (const int &v: g[u]) dfs(v, u), sa[u] += sa[v];
c[0][u] = (u == nc ? -inf : sa[u] - b[fa]);
} // dfs
int main(void) {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
for (int i = 1; i <= m; ++i)
scanf("%d%d%lld", &e[i].u, &e[i].v, &e[i].w);
sort(e + 1, e + m + 1);
for (int i = 1; i <= n; ++i) fa[i] = i;
nc = n;
for (int i = 1; i <= m; ++i) {
int u = e[i].u, v = e[i].v;
int64_t w = e[i].w;
int fu = fnd(u), fv = fnd(v);
if (fu != fv) {
++nc, fa[nc] = nc;
b[nc] = w;
fa[fu] = nc, fa[fv] = nc;
g[nc].push_back(fu);
g[nc].push_back(fv);
}
}
memset(c, inf, sizeof(c));
dfs(nc, 0);
for (int j = 1; j < LOG; ++j) for (int i = 1; i <= nc; ++i)
c[j][i] = min(c[j - 1][i], c[j - 1][par[j - 1][i]]);
while (q--) {
int x;
int64_t w;
scanf("%d%lld", &x, &w);
if (b[par[0][x]] > w + a[x]) {
printf("%lld\n", w + a[x]);
} else {
int u = x;
for (int j = LOG - 1; j >= 0; --j)
if (w + c[j][u] >= 0) u = par[j][u];
printf("%lld\n", sa[u] + w);
}
}
exit(EXIT_SUCCESS);
} // main