HBC236764[ZJOI2010]NETWORK 网络扩容,费用流,网络流,图论霜雪千年题解

凌晚轩算法基础篇 2023-11-13 02:23:01 46 0

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

n1条边连接且保证联通，年都被暴风雪袭击那么这个国家将会被冰封，定义一年世界的混乱程度为所有未冰封国家组成的生成子图的联通块数量，m年中每一年的混乱程度之和的期望值。

枫红十里长街红帘后谁人蹙着眉遥梦桑竹桃源轮回中曾道别的地点愿今生再相见消融你眉间悲戚霜雪世界由 n n 个国家组成，由 n-1 n−1 条边连接且保证联通。 m m 年之中，在第 i i 年暴风雪会随机袭击 a_i a i 个国家。第 i i 个国家的抗寒能力为 b_i b i ，如果这个国家连续 b_i b i 年都被暴风雪袭击那么这个国家将会被冰封（但没有暴风雪的那一年会马上解冻）。定义一年世界的混乱程度为所有未冰封国家组成的生成子图的联通块数量。求世界 m m 年中每一年的混乱程度之和的期望值。