#BZOJ2888. 资源运输
-
ID: 1369
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
资源运输
No submission language available for this problem.
题目描述
小Y盯上了最近发行的即时战略游戏——ResourceTransport。但在前往通关之路的道路上，一个小游戏挡住了小Y的步伐。“国家的本质是生产与收集资源”是整款游戏的核心理念，这个小游戏也不例外。简单的说，用户需要管理一个国家，使其繁荣富强。
一个国家含有N个城市，游戏开始时城市间没有任何道路。城市可以通过高速公路连接。为了减少建设费用，每对城市间最多存在一条路径。
小Y拥有极强的游戏天赋，很快就把所有城市的生产能力提到了满级，把高速公路的建设费用修改成了0。
悲剧的是，对于每个连通的城市群，都要把该城市群中的某个城市设立成资源集合处，小Y把这件事忘了；更悲剧的是，建造高速公路这件事，小Y也忘了。
可小Y是个完美主义者，他请来了你帮他设立资源集合处，自己负责建造高速公路。假设连通城市群中的某个城市i到该城市群的资源集合处最少需要经过Di条高速公路，那么总运输费用为Sigma(Di)。你需要在每个连通城市群中设立一个资源集合处，使得总费用最小。小Y有时会向你询问此时最小的总费用。
问题很简单，麻烦的是小Y会在你好不容易算出最小总费用时建造一条新的高速公路。由于每个连通的城市群只能有一个资源集合处，所以最小总费用又得重新计算，这可真是个苦差事……
输入格式
第一行两个整数N，M分别表示国家中的城市数与小Y的操作数。
接下来M行，每行可能为：
1.A x y：表示在城市x和城市y间建造一条高速公路，保证此操作出现N-1次；
2.Q：表示小Y询问此时的最小总费用。
输出格式
对于每个Q操作，单独输出一行一个整数Ans，表示所求的答案。
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
0 4 12 【样例解释】 1.开始所有城市互不联通，每个城市都是资源集合处，费用为0； 2.后来分别把城市1、城市4、城市7、城市8设立为资源集合处，费用为4； 3.最后把城市4设立为资源集合处，费用为12。
数据范围与约定
N<=40000,M<=80000