#P11729. [集训队互测 2015] Marketing network

[集训队互测 2015] Marketing network

题目描述

“世界充满着各种 if,我们存在着的这个世界也不过是为数众多的 if 的结果中的一个,而未来则更是由于无限的 if 而混沌流动着的世界。”

在某一条世界线中,你可能正在经营一个跨国公司,想想是不是有点激动呢。在那一个世界中,你正被营销网络的设计问题所困扰。

你的跨国公司在 nn 个国家设立了销售网点,国家由 11nn 编号,这 nn 个国家由 mm 条双向航线连接。如果把国家看作结点把航线看作边,可以抽象成一个无向图。

你已经在其中的 SS 个国家设立了分公司。你会买下一些航线的 VIP 以加速你的商品运输。

无论这条世界线出了什么偏差,你是 OIer 这个事实是不会改变的,所以你对 VIP 航线购买方案有着苛刻的要求:

  1. 以任意一个国家作为出发点,都无法只经过 VIP 航线且不经过重复的国家回到出发点。即购买的 VIP 航线形成原图的一个生成森林。
  2. 从任意一个分公司出发都可以只经过 VIP 航线到达另一个分公司。

每条航线都有一个权值,表示购买该航线的 VIP 的费用。敏锐的你一定一眼发现了完成目标的最小总花费。但是这样不够任性不够土豪,这势必会影响公司未来的发展。于是机智的你决定求出总费用前 kk 小的 VIP 航线购买方案。

两个 VIP 航线购买方案被认为是不同的,当且仅当存在至少一条航线只在其中一个购买方案中被买为 VIP。

“if 只是单纯的 if 罢了。就算有这样一个存在着 good if 的平行世界,人类也不是能简单地跨过世界线,去到那里的。”

但是小小地遐想一下还是很美好的,所以就请你解决这个问题吧。

简要题意:求出前 kk 小的生成森林,要求给定的 SS 个点在森林中两两可达。

输入格式

第一行,四个正整数 n,m,S,kn, m, S, k

第二行,SS 个正整数,表示分公司所在的国家,保证读入的国家编号互不相同。

接下来 mm 行,每行三个正整数 uiviciu_i,v_i,c_i,表示国家 uiu_iviv_i 之间有一条费用为 cic_i 的航线。保证 1ui,vin1 \leq u_i, v_i \leq n,且 uiviu_i \neq v_i

输出格式

输出 kk 行,每行一个正整数,第 ii 行的正整数表示总费用第 ii 小的 VIP 航线购买方案的总费用。

6 9 3 6
3 1 5
1 2 1
1 3 2
3 2 2
2 4 5
3 4 5
3 5 2
3 6 2
6 4 4
5 6 1
4
5
5
5
5
6

提示

数据范围

除题面样例外的,航线和分公司所在国家均是在 n,m,Sn, m, S 固定的情况下均匀随机生成的。对于所有航线,cic_i 是从 11100100 的整数中均匀随机选取的。

保证一定存在至少 kk 种不同的 VIP 航线购买方案。

(本题洛谷测试点编号较为混乱,下方表格仅作各个测试点范围的大致参考,实际评测中测试点编号与表格无关)

测试点编号 nn mm SS kk
151\sim 5 =10=10 =20=20 =4=4 =10=10
6106\sim 10 =50=50 =100=100 =10=10 =1=1
111511\sim 15
162016\sim 20 =5=5 =20=20
212521\sim 25 =7=7 =50=50
263026\sim 30 =9=9
313531\sim 35 =10=10
364036\sim 40 =11=11
414541\sim 45 =13=13
465046\sim 50 =15=15