QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 7871. 命运

统计

列车必将驶向下一站,而舞台将前往何处?你们又将前往何处?

在此刻,你扮演着「观众」 ,$ n $ 位舞台少女的人生因你所选择的「命运」 而交织在一起。

为了方便理解,我们用一个三元组 $ (u,v,w) $ 来描述一条连接编号为 $ u,v $ 的舞台少女,羁绊值为 $ w $ 的「命运」。

可是,舞台少女的「命运」并不完全被你所掌握。编号为 $ s $ 的舞台少女 Karen 酱,支配着与她自己有关的「命运」。具体地,若一条「命运」$ (u,v,w) $ 满足 $ u=s \lor v=s $ ,则这条「命运」被 Karen 酱支配着。被 Karen 酱支配的「命运」你无权干涉。而其余的「命运」则可供你自由支配。

你将从你所支配的「命运」中选择 $ a $ 条出来( $ a $ 是一个由你选择的非负整数),而 Karen 酱则必须选择恰好 $ k $ 条与她有关的「命运」。然后,演出开始。

我们称两位舞台少女的人生是有交集的,当且仅当她们被「命运」直接或间接地连接着。

Karen 酱不喜欢无意义的「命运」,所以她要求自己不能与同一个人直接连接着多条「命运」; Karen 酱也不希望看见大家渐行渐远,所以她要求所有 $ n $ 位舞台少 女的人生都相互有交集,否则将会罢演。

设最终选择的 $ a+k $ 条「命运」的羁绊值所构成的集合为 $ A $ ,定义 $ A $ 的颠沛值为:

$$\sum_{i=1}^{a+k}{\rm max_i}(A)\times (10^9+7)^{-i}$$

其中 $ {\rm max}_i(A) $ 表示集合 $ A $ 中第 $ i $ 大的数。 「观众」和舞台少女密不可分,现在你需要和 Karen 酱合作,一同献上颠沛值最小的演出。为了方便,你只需要输出你们最终选择的「命运」的羁绊值之和。 若不存在满足 Karen 酱要求的演出,则输出 nonnondayo

形式化题意

给定 $ m $ 条边,你需要选出若干条边满足图联通并且编号为 $ s $ 的点度数恰为 $ k $。并且与 $ s $ 有关的边不能选择重边。找到一种上述式子最小的方案并输出选择的边权和。 无解输出 nonnondayo

输入格式

第一行四个整数 $ n,m,k,s $。

接下来 $ m $ 行,每行三个整数 $ u,v,w $ 表示一条「命运」。

输出格式

一行一个整数表示你们最终选择的「命运」的羁绊值之和,不存在方案则输出 nonnondayo

样例 1

input

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

output

6

数据范围

对于所有数据满足 $ 1\leq k<n\leq 5\times 10^4 $,$ m\leq 5\times 10^5,w\leq 10^9 $。有重边无自环,$ w_i $ 互不相同。

  • 子任务 1(5 分):$ m=n-1 $。
  • 子任务 2(10 分):$ n,m\leq 21 $。
  • 子任务 3(15 分):$ n\leq 1000 $,$ m\leq 3\times 10^3 $。
  • 子任务 4(20 分):保证去掉编号为 $ s $ 的点和与 $ s $ 有关的边后,剩下的图为森林。
  • 子任务 5(10 分):满足恰有 $ k $ 条边 $ (u_i,v_i) $ 满足其中一个端点为 $ s $&ZeroWidthSpace; 。
  • 子任务 6(20 分):$ n\leq 10^4 $,$ m\leq 10^5 $。
  • 子任务 7(20 分):$ n\leq 5\times 10^4 $,$ m\leq 5\times 10^5 $。