Luogu3232 [HNOI2013] 游走

题意：有一个 个点 条边的无向图，边权是一个排列。

从 出发，每次随机选一条出边移动，同时费用加上该边边权。

请合理地安排边权，使得期望费用最大。

，时限 。

---

显然边权乘以期望经过次数就是期望花费，所以按照期望经过次数贪心赋权即可。

边数可能达到 ，不好下手，先从点考虑。

若一个点共有 条出边，那么从该点走出的一步会给所有相邻的边 的期望经过次数贡献。

那么，若该点期望经过 次，则对相邻的所有边有 的贡献。

这样，我们只需要求出所有点的期望经过次数即可。

设 边 存在， 为 的度数，可以列式:

由于 点不会走出来，不能考虑其贡献。

高斯消元即可，复杂度 。