输入文件中string居然有\n 需要while(cin>>str)s+=str;坑！

回复 @cstdio :
这个解题过程太酷炫了

我有一个证明，但这里空白太小，写不下

受益匪浅

快排~

MST。介绍一下Prim吧。
根据题意，也不难理解什么是MST。
首先，MST具备以下2条重要的性质：
1.最优子结构；W(T)=W((u,v))+W(T1)+W(T2);(T1,T2为两棵子树，而(u,v)为连接这两棵树的边，即你切断的那条边)
2.重叠子结构；(最终均可化简至有限的相同的基本问题)
看似可以DP，但是，对于MST，不难发现还具备这条性质(其实是一个简单的定理)：
若将图G(V,E)化成2个部分，A和G-A，则若存在边(u,v)∈E使得A与G-A联通，则E(Min)∈MST.
这条定理告诉我们MST具备“局部最优解同时也是全局最优解“的属性；
而具备该属性则说明存在某种贪心策略可以生成MST。
Prim算法就是用到了这条定理来完成的。其实它和迪杰斯特拉很像。对于邻接表储存的稀疏图，加上二叉堆后可大大提高算法的速度。
当然，用斐波那契堆优化可达到极为拔群的效果。

已吓傻……为何突然冒出来这么多……

回复 @Strawberry :
ORZ

直接动规，果断慢成翔

我会写网络流了哈哈

回复 @cstdio :
小号旺。。。

喵的又跪在忘开long long上了……

这题纳尼情况。。。那两个奇怪的字符哪来的。。。

回复 @常可神牛 :
第八个点同挂

回复 @cstdio :
我好像。。。看见了一个id 。。。野生的38跳了出来。。。

机智地删去了模板里一些没用的东西就rank1了= =
这题没必要用lazy标记的
现在rank1的是小号，╭(╯^╰)╮

纯模拟居然A了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

回复 @法法桶 :
说得好

时间快的让我感到不科学

严重表示对题重交可耻 尤其是赵赵赵～