1 条题解
-
1
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; struct edge{ int u,v,w; }G[N]; int fa[N],cnt; long long ans; bool vis[N]; int find_root(int x){ if(fa[x]==x){ return x; } return fa[x]=find_root(fa[x]); } bool cmp(edge a,edge b){ return a.w>b.w; } int main(){ ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr); int n,k; cin>>n>>k; for(int i=0;i<=n;i++){ fa[i]=i; } for(int i=1;i<=k;i++){ int city; cin>>city; vis[city]=1; } for(int i=1;i<n;i++){ cin>>G[i].u>>G[i].v>>G[i].w; } sort(G+1,G+n,cmp); for(int i=1;i<n;i++){ int u=G[i].u,v=G[i].v,w=G[i].w; int x=find_root(u),y=find_root(v); if(vis[x]&&vis[y]){ ans+=w; } else{ fa[x]=y; vis[y]=vis[x]||vis[y]; } } cout<<ans; return 0; }
信息
- ID
- 6735
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 6
- 标签
- 递交数
- 5
- 已通过
- 2
- 上传者