首页 > 题解 > bzoj 2322 [BeiJing2011]梦想封印

bzoj 2322 [BeiJing2011]梦想封印

Description

渐渐地,Magic Land上的人们对那座岛屿上的各种现象有了深入的了解。
为了分析一种奇特的称为梦想封印(Fantasy Seal)的特技,需要引入如下的概念:
每一位魔法的使用者都有一个“魔法脉络”,它决定了可以使用的魔法的种类。
一般地,一个“魔法脉络”可以看作一个无向图,有N个结点及M条边,将结点编号为1~N,其中有一个结点是特殊的,称为核心(Kernel),记作1号结点。每一条边有一个固有(即生成之后再也不会发生变化的)权值,是一个不超过U的自然数。
每一次魔法驱动,可看作是由核心(Kernel)出发的一条有限长的道路(Walk),可以经过一条边多次,所驱动的魔法类型由以下方式给出:
将经过的每一条边的权值异或(xor)起来,得到s。
如果s是0,则驱动失败,否则将驱动编号为s的魔法(每一个正整数编号对应了唯一一个魔法)。
需要注意的是,如果经过了一条边多次,则每一次都要计入s中。
这样,魔法脉络决定了可使用魔法的类型,当然,由于魔法与其编号之间的关系尚未得到很好的认知,此时人们仅仅关注可使用魔法的种类数。
梦想封印可以看作是对“魔法脉络”的破坏:
该特技作用的结果是,“魔法脉络”中的一些边逐次地消失。
我们记总共消失了Q条边,按顺序依次为Dis1、Dis2、……、DisQ。
给定了以上信息,你要计算的是梦想封印作用过程中的效果,这可以用Q+1个自然数来描述:
Ans0为初始时可以使用魔法的数量。
Ans1为Dis1被破坏(即边被删去)后可以使用魔法的数量。
Ans2为Dis1及Dis2均被破坏后可使用魔法的数量。
……
AnsQ为Dis1、Dis2、……、DisQ全部被破坏后可以使用魔法的数量。

Input

第一行包含三个正整数N、M、Q。
接下来的M行,每行包含3个整数,Ai、Bi、Wi,表示一条权为Wi的与结点Ai、Bi关联的无向边,其中Wi是不超过U的自然数。
接下来Q行,每行一个整数:Disi。

Output

一共包Q+1行,依次为Ans0、Ans1、……、AnsQ。

Sample Input

【输入样例1】

3 3 2
1 2 1
2 3 2
3 1 4
1
3

【输入样例2】

5 7 7
1 2 1
1 3 1
2 4 2
2 5 2
4 5 4
5 3 9
4 3 1
7
6
5
4
3
2
1

Sample Output

【输出样例1】

5
2
0

【样例1解释】

初始时可使用编号为1、3、4、6、7的魔法。

在删去第1条边(连结1、2结点的边)后,可使用4和6号魔法。

第3条边(连结第1、3结点的边)也被删去后,核心(Kernel)即结点1孤立,易知此时无法使用魔法。

【输出样例2】

15
11
5
2
2
1
1
0

HINT

【数据规模和约定】

所有数据保证该无向图不含重边、自环。

所有数据保证不会有一条边被删除多次,即对于不同i和j,有Disi≠Disj

30%的数据中N ≤ 50,M ≤ 50,Q ≤50,U≤100;

60%的数据中N ≤ 300,M ≤ 300,Q ≤50,U≤10^9;

80%的数据中N ≤ 300,M ≤ 5000,Q ≤5000,U≤10^18;

100%的数据中N ≤ 5000,M ≤ 20000,Q ≤20000,U≤10^18;

题解

找了个挺好的题解

这种分类讨论题的结论挺难写的。。但是实现倒是挺好搞的


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×