CF1023F Mobile Phone Network

恶臭树链剖分毁我青春耗我钱财不讲武德。

题目大意

给出 \(k\) 条边权未定的边,以及 \(m\) 条边权已定的边,让你求这样一个东西:

  1. 有一颗最小生成树包含这 \(k\) 条边;

  2. 这 \(k\) 条边的权值和最大。

最后输出 \(k\) 条边的权值和。

既然要求 \(k\) 条边都在最小生成树内,那我们不妨先把这 k 条边加入一棵树内。

然后我们对 \(m\) 条边按边权排序,从小到大把能加入生成树内的边都加进去。(其实就是补完这颗生成树)

然后我们考虑剩下没加的边。

CF1023F Mobile Phone Network

如上图,红色二边是 \(k\) 条边中的两条,蓝色是已加入的边,而黑边则是,未加入的一条黑边。

考虑这条边会对边 \(AC\) 和 \(AB\) 造成什么影响。

因为我们优先按边权从小到大排了一遍,所以只要红边中的最大值 \(\le\) \(f_{w_i}\) ,那么蓝边就必定可以加入最小生成树中。

那么每一条黑边其实就变成了对路径的限制。

即 \(f_{a_i}\) 到 \(f_{b_i}\) 的路径上的边的权值不得超过 \(f_{w_i}\) ,这是一个在树上进行区间覆盖的模板,可以用树剖轻松解决。

还有亿些小问题:

  1. 初始的红边要设成一个最大值,这样就易于进行判断是否有解;

  2. 蓝边的权值设为 \(0\) ,这样就不会影响到最大值的更新。

以上。

Code

#include <stdio.h>
#include <algorithm>
#include <string.h>
#define N 500005
using namespace std;
const int INF=1e9+1;
int n, m, k, ans[N];
struct Edge{
	int to, nxt, w;
}d[N*2];
int tot, h[N];
void add(int x, int y, int w){
	d[++tot].to=y, d[tot].nxt=h[x];
	d[tot].w=w, h[x]=tot;
}
struct Tree_chain_partition{
	int val[N], son[N], sum[N], dep[N], fa[N];
	int top[N], toseg[N], back[N], cnt;
	void debug(){
		for(int i=1; i<=n; i++) 
			printf("%d: %d %d %d %d %d %d %d %d\n", i, val[i], son[i], sum[i], dep[i], fa[i], top[i], toseg[i], back[i]);
		for(int i=1; i<=n; i++)
			printf("--%d %d\n", mx[i], tag[i]);
	}
	void dfs_1(int pos, int f){
		sum[pos]=1, dep[pos]=dep[f]+1, fa[pos]=f;
		for(int i=h[pos]; i; i=d[i].nxt){
			int to=d[i].to;
			if(to==f) continue;
			val[to]=d[i].w;
			dfs_1(to, pos);
			sum[pos]+=sum[to];
			if(sum[son[pos]]<sum[to]) son[pos]=to; 
		}
	}
	void dfs_2(int pos, int root){
		toseg[pos]=++cnt, top[pos]=root;
		back[cnt]=pos;
		if(son[pos]) dfs_2(son[pos], root);
		for(int i=h[pos]; i; i=d[i].nxt){
			int to=d[i].to;
			if(top[to]) continue;
			dfs_2(to, to);
		}
	}
	#define ls k<<1
	#define rs k<<1|1
	#define mid (l+r>>1)
	int mx[N*4], tag[N*4];
	void pushup(int k){mx[k]=max(mx[ls], mx[rs]);}
	void upd(int k, int w){mx[k]=w, tag[k]=w;}
	void pushdown(int k){
		if(!tag[k]) return ;
		if(mx[ls]>=tag[k]) upd(ls, tag[k]);
		if(mx[rs]>=tag[k]) upd(rs, tag[k]);
		tag[k]=0;
		return ;
	}
	void build(int k, int l, int r){
		if(l==r){mx[k]=val[back[l&r]];return ;}
		build(ls, l, mid);build(rs, mid+1, r);
		pushup(k);
	}
	void add(int k, int l, int r, int x, int y, int w){
		if(w>mx[k]) return ;
		if(x<=l&&r<=y) return upd(k, w);pushdown(k);
		if(x<=mid) add(ls, l, mid, x, y, w);
		if(mid<y) add(rs, mid+1, r, x, y, w);
		return pushup(k);
	}
	int LCA(int a, int b){
		while(top[a]!=top[b]){
			if(dep[top[a]]<dep[top[b]]) swap(a, b);
			a=fa[top[a]];
		}
		if(dep[a]>dep[b]) return b;
		return a;
	}
	void change(int a, int b, int w){
		while(top[a]!=top[b]){
			if(dep[top[a]]<dep[top[b]]) swap(a, b);
			add(1, 1, n, toseg[top[a]], toseg[a], w);
			a=fa[top[a]];
		}
		if(a==b) return;
		if(dep[a]<dep[b]) swap(a, b);
		add(1, 1, n, toseg[b]+1, toseg[a], w);
	}
	void putall(int k, int l, int r){
		if(l==r){
			ans[back[l&r]]=mx[k];
			return ;
		}pushdown(k);
		putall(ls, l, mid);putall(rs, mid+1, r);
	}
}TCP;
struct F{
	int a, b, w;
	bool in;
	bool operator < (const F &A) const{
		return w<A.w;
	}
}f[N], g[N];
int fs[N];
int find(int x){
	if(x==fs[x]) return x;
	return fs[x]=find(fs[x]);
}
long long ret=0;
int main(){
	scanf("%d%d%d", &n, &k, &m);
	for(int i=1; i<=n; i++) fs[i]=i;
	for(int i=1; i<=k; i++){
		scanf("%d%d", &g[i].a, &g[i].b);
		add(g[i].a, g[i].b, INF), add(g[i].b, g[i].a, INF);
		fs[find(g[i].a)]=find(g[i].b);
	}
	for(int i=1; i<=m; i++)
		scanf("%d%d%d", &f[i].a, &f[i].b, &f[i].w), f[i].in=false;
	sort(f+1, f+m+1);
	for(int i=1; i<=m; i++){
		int fa=find(f[i].a), fb=find(f[i].b);
		if(fa==fb) continue;
		f[i].in=true;
		fs[fa]=fb;
		add(f[i].a, f[i].b, 0);
		add(f[i].b, f[i].a, 0);
	}
	TCP.dfs_1(1, 0);
	TCP.dfs_2(1, 1);TCP.top[1]=TCP.fa[1]=1;
	TCP.build(1, 1, n);
	for(int i=1; i<=m; i++)
		if(!f[i].in){
			int lca=TCP.LCA(f[i].a, f[i].b);
			TCP.change(f[i].a, lca, f[i].w);
			TCP.change(f[i].b, lca, f[i].w);
		}
	TCP.putall(1, 1, n);
	for(int i=1; i<=n; i++){
		if(ans[i]==INF) return printf("-1")*0;
		ret+=(long long)ans[i];
	}
	printf("%lld\n", ret);
	return 0;
}
上一篇:阿里云短信业务


下一篇:PHP中相关正则表达式的函数与常用正则表达式