【题解】P4550 收集邮票
题目大意
有\(n(n\le 10000)\)种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是购买,每次只能买一张,并且买到的邮票究竟是\(n\)种邮票中的哪一种是等概率的,概率均为\(\frac{1}{n}\)。购买第\(k\)次邮票需要支付\(k\)元钱。
求得到所有种类的邮票需要花费的钱数目的期望。
给出一个有\(n\)个节点\(m\)条边的无向图,节点编号为\(1-n\),边编号为\(1-m\)。初始时小E同学在\(1\)号节点。数据可能包含重边和自环。
每条边都有一个妖怪住在边上。在节点\(1\)处有两种守护精灵A,B,每种都有无数个。无向图中每条边都有权值\(a_i\)和\(b_i\),当且仅当小E身上携带的A守护精灵不少于\(a_i\),且B守护精灵不少于\(b_i\),这条边上的妖怪不会对通过这条边的人发起攻击。
求在不被妖怪袭击的情况下,到\(n\)号节点最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的个数与 B 型守护精灵的个数之和。
\(2\le n \le 50000, 0\le m \le 100000, 1\le a_i,b_i \le 50000\)