题意简单思路也还可以。开始从小到大排序非常烦。后来从大到小就很简单了;

从大到小解决了删除的边最小。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 100010
using namespace std;
#define LL long long
struct node
{
int x,y;
LL v;
}edge[maxn];
int pa[maxn],n,m,vis[maxn];
bool cmp(node a,node b)
{
return a.v>b.v;
}
void init()
{
int i;
for(i=;i<=n;i++)
pa[i]=i;
}
int find (int x)
{
if(x!=pa[x])
pa[x]=find(pa[x]);
return pa[x];
}
void kruskal()
{
int i,j;
LL ans=;
for(i=;i<n-;i++)
{
int fx=find(edge[i].x);
int fy=find(edge[i].y);
if(vis[fx]&&vis[fy])
{
ans+=edge[i].v;
}
else if(vis[fx])
pa[fy]=fx;
else if(vis[fy])
pa[fx]=fy;
else pa[fx]=fy;
}
printf("%I64d\n",ans);
}
int main()
{
int i,j,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
memset(vis,,sizeof(vis));
for(i=;i<n-;i++)
{
scanf("%d%d%lld",&edge[i].x,&edge[i].y,&edge[i].v);
}
for(i=;i<m;i++)
{
int c;
scanf("%d",&c);
vis[c]=;
}
sort(edge,edge+n-,cmp);
kruskal();
}
}

最新文章

  1. 小小改动帮你减少bundle.js文件体积(翻译)
  2. Workerman-文件监控-牛刀小试
  3. Spring学习笔记之一----基于XML的Spring IOC配置
  4. @MappedSuperclass的用法
  5. Spring.Net Remoting 相关使用
  6. uva----(100)The 3n + 1 problem
  7. Mysql性能优化那些事
  8. iTween visual Editor 0.6.1
  9. 删除链表的中间节点和a/b处节点
  10. route命令实例练习
  11. js的赋值问题:值传递还是引用传递?
  12. jquery 树形导航菜单无限级
  13. 【Android开发经验】android:windowSoftInputMode属性具体解释
  14. 《ERP系统修正数据的sql文件》
  15. java中线程池的使用
  16. Homebrew安装与使用
  17. system v 共享内存
  18. 2018.11.04 洛谷P1081 开车旅行(倍增)
  19. 【BZOJ】【2120】数颜色 &amp; 【2453】维护队列
  20. R语言低级绘图函数-grid

热门文章

  1. Python的几个高级编程技巧
  2. mysql api 不支持source命令
  3. VMWare下载安装以及创建虚拟机教程
  4. 2019-8-31-dotnet-通过-WMI-获取指定进程的输入命令行
  5. jmeter断言步骤
  6. TZOJ 5110 Pollutant Control(边数最少最小割最小字典序输出)
  7. Nonsense Time
  8. CodeForces - 627A
  9. php数据几行代码导出到excel(非插件)
  10. sql作业启停服务器