主题

主题

 
   

2001: [Hnoi2010]City 城市建设

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=2001/http://cogs.pro/cogs/problem/problem.php?pid=1754

【题目描述】

PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和, Louis决定求助于你来完成这个任务。

【输入格式】

文件第一行包含三个整数N,M,Q,分别表示城市的数目,可以修建的道路个数,及收到的消息个数。 接下来M行,第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi,Yi≤n, 0≤Zi≤50000000),表示在城市Xi与城市Yi之间修建道路的代价为Zi。接下来Q行,每行包含两个数k,d,表示输入的第k个道路的修建代价修改为d(即将Zk修改为d)。

【输出格式】

输出包含Q行,第i行输出得知前i条消息后使城市连通的最小花费总和。

【样例输入】

5 5 3

1 2 1

2 3 2

3 4 3

4 5 4

5 1 5

1 6

1 1

5 3

【样例输出】

14

10

9

【数据规模】

对于20%的数据, n≤1000,m≤6000,Q≤6000。

有20%的数据,n≤1000,m≤50000,Q≤8000,修改后的代价不会比之前的代价低。

对于100%的数据, n≤20000,m≤50000,Q≤50000。


个人解法:

尝试了传说中的线段树分治。

主要是有了BZOJ4025的基础,就觉得没有那么难了。虽然二者似乎并没有很大关系?

我们对时间建线段树,一条边可以拆分为若干条边,使得这些边权值不变,出现的时间交集为0,并集为[0..q]。

这里边的数量是O(m+q)的,但是事实上我们也不需要O(m+q)的空间去储存,处理一下就可以了。

正是因为上面那一条很重要的性质,才使得我们在处理的时候不用叽叽歪歪考虑很多很复杂的情况。

接下来把这些边按照时间挂在线段树的节点上。

叶子节点就是最终状态,这一个状态对应的图的边就是这个叶子节点到根的所有节点的边。

那么我们用一棵LCT维护我们的最小生成树,顺便维护整棵树的权值,化边为点。如果无环则直接连接。如果有环,则删去最大的边。并记录下来。回溯的时候把操作全部撤销。

LCT的点数是O(n+m)的。

总的时间复杂度是O((m+q)*logq*log(m+q))。LCT常数巨大。卡常失败。


一个优化:

LCT常数实在是太大了。

发现我们在判断是否存在环的时候,拿LCT可以需要O(6logn)-O(8logn)的时间。于是我们可以选择并查集,做到O(logn)的时间。

注意一个性质:环切的时候连通性是不变的。


我如同网上所有人,看到别人卡常失败自己总是想去尝试,然后一失败告终。

最大数据:


然而本题时限2s……


大概是这样了……#17点时过时不过……


代码如下:

http://cogs.pro/cogs/submit/code.php?id=386057


这个故事告诉我们,卡卡常可以愉悦身心。

 
 
评论