[bzoj2466]:[中山市选2009]树

Description

给定一棵树,每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了,那么该节点的灯会从熄灭变为点亮(当按之前是熄灭的),或者从点亮到熄灭(当按之前是点亮的)。并且该节点的直接邻居也发生同样的变化。

开始的时候,所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。

阅读更多

[bzoj3143]:[Hnoi2013]游走

Description

一个无向连通图,顶点从1编号到N,边从1编号到M。
小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。
现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。

阅读更多