无法接受自己sT1T2没写出来

UPD 老师已经开大时间限制 已加上第二次评测的记录

我在写这篇题解的时候cogs上时间限制还是1秒，cogs评测机显然不符合CCFIntel Core Ultra 9 285K CPU @ 3.70 GHz的标准，在洛谷和云斗AC的代码，再加上卡常也88分，最慢的1.099s，所以我打扰了老师开大时限，但老师可能比较忙没有回复，所以这篇题解在cogs上的分数按照1s为准。

题意

给你一张$N$个点无向图，保证任意两个点之间都是联通的。

另外还有$K$个额外的点，你可以从这$K$个点里任意选择若干个点，选择第$j$个点的代价为$c_j$，然后对于每个选择的点都可以往原本$N$个点连无向边，第$j$个额外点对第$i$个原有点连边的代价为$a_{j,i}$。

现在求出这张图的MST。

$1 \leq N \leq 10^4$

$1 \leq M \leq 10^6$

$0 \leq K \leq 10$

思路

考场淘汰回放：

把T1当成dp死做半天做不出来之后看第二题，一眼看第二题，先写出了60分左右的解法，代码还写了半天，结果一直以为和最短路有什么关系，恶心半天写不出来了

40~60分

直接把所有的边放到图里，包括额外点的连边。

排序所有边之后，枚举选额外点的状态跑kruskal即可。

粗略估计时间复杂度$O(2^k * (M+NK))$（一共会有$M+NK$条边，枚举状态$2^k$）

不是满分，来看我回忆代码，不加赛时卡常，在cogs上就32分 云斗上80分 洛谷上88分

UPD:开大时间限制后cogs80分

http://218.28.19.228:8081/cogs/submit/code.php?id=7XieaPkPU

https://www.yundouxueyuan.com/record/69072490b8ccc474dc719cef

https://www.luogu.com.cn/record/245035597

100分

我们最终选的边肯定包括了不考虑额外点的最小生成树里，所以先对原图跑一遍最小生成树，只保留树边，然后再枚举状态跑kruskal其实就做完了。

时间复杂度$O(M log M + 2 ^ k * (N - 1 + NK))$

目前卡常在cogs88分，洛谷和云斗不卡常就是满分

UPD:100分了