Codeforces Gym 103446H. Life is a Game

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

上一篇:08 分布式计算MapReduce--词频统计


下一篇:oracle 密码过期解决办法