首页 > 代码库 > 【BZOJ-2888】资源运输 LCT + 启发式合并

【BZOJ-2888】资源运输 LCT + 启发式合并

2024-09-05 17:23:19   218人阅读

2888: 资源运输

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 63  Solved: 33
[Submit][Status][Discuss]

Description

       小Y盯上了最近发行的即时战略游戏——ResourceTransport。但在前往通关之路的道路上，一个小游戏挡住了小Y的步伐。“国家的本质是生产与收集资源”是整款游戏的核心理念，这个小游戏也不例外。简单的说，用户需要管理一个国家，使其繁荣富强。
       一个国家含有N个城市，游戏开始时城市间没有任何道路。城市可以通过高速公路连接。为了减少建设费用，每对城市间最多存在一条路径。
       小Y拥有极强的游戏天赋，很快就把所有城市的生产能力提到了满级，把高速公路的建设费用修改成了0。
悲剧的是，对于每个连通的城市群，都要把该城市群中的某个城市设立成资源集合处，小Y把这件事忘了；更悲剧的是，建造高速公路这件事，小Y也忘了。
可小Y是个完美主义者，他请来了你帮他设立资源集合处，自己负责建造高速公路。假设连通城市群中的某个城市i到该城市群的资源集合处最少需要经过Di条高速公路，那么总运输费用为Sigma(Di)。你需要在每个连通城市群中设立一个资源集合处，使得总费用最小。小Y有时会向你询问此时最小的总费用。
问题很简单，麻烦的是小Y会在你好不容易算出最小总费用时建造一条新的高速公路。由于每个连通的城市群只能有一个资源集合处，所以最小总费用又得重新计算，这可真是个苦差事……

Input

第一行两个整数N，M分别表示国家中的城市数与小Y的操作数。
接下来M行，每行可能为：
       1.A x y：表示在城市x和城市y间建造一条高速公路，保证此操作出现N-1次；
       2.Q：表示小Y询问此时的最小总费用。

Output

       对于每个Q操作，单独输出一行一个整数Ans，表示所求的答案。

Sample Input

8 10
Q
A 1 2
A 4 5
A 6 7
A 3 4
Q
A 2 5
A 6 8
A 4 6
Q

Sample Output

0
4
12
【样例解释】
1.开始所有城市互不联通，每个城市都是资源集合处，费用为0；
2.后来分别把城市1、城市4、城市7、城市8设立为资源集合处，费用为4；
3.最后把城市4设立为资源集合处，费用为12。

HINT

N<=40000,M<=80000

Source

Solution

首先可以发现，对于森林中的每棵树，资源集合处都应该是重心。

所以对森林，维护每个树的重心。

问题在于合并两棵树时快速得到新树的重心，只能暴力重构。

不过考虑把小的一棵树拆开，一个一个点的加入大的一棵树中，这样就可以得到新树的重心了（保持原有重心或者向加点方向移动一步）。

维护答案需要维护子树到重心的距离和，那么加入一个新点，相当于链上加一个等差数列。

等差数列标记显然是可以合并的，注意下放的时候，如果向左子树下放则需要加上右子树的贡献，因为LCT中的右子树是其左子树的后代。

这样启发式合并的复杂度就是$O(Nlog^{2}N)$，不过直接写数组的常数有点略大会TLE..所以改成了结构体。

Code

#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>using namespace std;inline int read(){	int x=0,f=1; char ch=getchar();	while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}	while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}	return x*f;}#define MAXN 40010int N,M,ans;struct EdgeNode{	int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}namespace LCT{		int sz;	struct LCTNode{		int son[2],fa,size,tag,val,a1,d,sum;	}t[MAXN];		inline bool isroot(int x) {return t[t[x].fa].son[0]!=x&&t[t[x].fa].son[1]!=x || !t[x].fa;}		inline void Update(int x) {if (!x) return; t[x].size=t[t[x].son[0]].size+t[t[x].son[1]].size+1;}		inline void Modify(int x,int v) {if (!x) return; t[x].tag+=v; t[x].val+=v;}		inline void Change(int x,int _a1,int _d) {if (!x) return; t[x].a1+=_a1; t[x].d+=_d; t[x].sum+=_a1+t[t[x].son[1]].size*_d;}		inline void Pushdown(int x)	{		if (!x) return;		if (t[x].tag) Modify(t[x].son[0],t[x].tag),Modify(t[x].son[1],t[x].tag),t[x].tag=0;		if (t[x].d) Change(t[x].son[0],t[x].a1+(t[t[x].son[1]].size+1)*t[x].d,t[x].d),Change(t[x].son[1],t[x].a1,t[x].d),t[x].a1=t[x].d=0;		}	    inline void Rotate(int x)    {        int y=t[x].fa,w=t[y].son[1]==x,z=t[y].fa;        t[y].son[w]=t[x].son[w^1];        if (t[x].son[w^1]) t[t[x].son[w^1]].fa=y;        if (t[z].son[0]==y) t[z].son[0]=x; else if (t[z].son[1]==y) t[z].son[1]=x;        t[x].fa=z; t[y].fa=x; t[x].son[w^1]=y;		Update(y);    }        int stack[MAXN];    inline void Splay(int x)    {        int tmp=x,top=0,y; stack[++top]=x;        while (!isroot(tmp)) stack[++top]=tmp=t[tmp].fa;        while (top) Pushdown(stack[top--]);        while (!isroot(x)) {            y=t[x].fa;            if (!isroot(y))                if ((t[t[y].fa].son[0]==y)^(t[y].son[0]==x)) Rotate(x);                	else Rotate(y);                Rotate(x);        }        Update(x);    }	        inline void Access(int x) {for (int y=0; x; y=x,x=t[x].fa) Splay(x),t[x].son[1]=y,Update(x);}		inline int Root(int x) {Access(x); Splay(x); while(t[x].son[0]) x=t[x].son[0]; return x;}		inline void Add(int x,int y)	{		t[x].fa=y; t[x].son[0]=t[x].son[1]=t[x].val=t[x].tag=t[x].sum=t[x].a1=t[x].d=0; t[x].size=1;		y=Root(y); Access(x); Splay(y); 		Modify(y,1); Change(y,0,1);		for (x=t[y].son[1]; t[x].son[0]; x=t[x].son[0]);		Splay(x); int v1=t[y].val,v2=t[x].val;		if ((v2<<1)>v1) {			t[x].val=v1; t[y].val-=v2;			t[y].sum-=t[x].sum+v2; t[x].sum+=t[y].sum+v1-v2;			Access(x); Splay(y); t[y].son[0]=x; t[y].son[1]=0;		}	} //push x into y		inline void DFS(int now,int last)	{		Add(now,last); 		for (int i=head[now]; i; i=edge[i].next)			if (edge[i].to!=last)				DFS(edge[i].to,now);	}		inline void Link(int x,int y)	{		int rx=Root(x),ry=Root(y);		ans-=t[rx].sum+t[ry].sum;		if (t[rx].val<t[ry].val) swap(x,y);		DFS(y,x); InsertEdge(x,y);		ans+=t[Root(x)].sum;	}}	int main(){		N=read(),M=read();	for (int i=1; i<=N; i++) LCT::t[i].val=LCT::t[i].size=1;		while (M--) {		char opt[2]; scanf("%s",opt+1);		switch (opt[1]) {			int x,y;			case ‘A‘ : x=read(),y=read(); LCT::Link(x,y); break;			case ‘Q‘ : printf("%d\n",ans); break;		}			}		return 0;}

【BZOJ-2888】资源运输 LCT + 启发式合并


联系
我们