5 5
1 2 4
1 3 -1
2 3 3
2 4 5
4 5 10
-1 10 10 1 1
9
最先的思路也是建立最小生成树 ，运用并查集的思路在连接两个并查集的时候判断是否用码头更加好 。卡在90%，可能是哪里打错了 ， 然后看到大神的做法 ， 虚拟出一个点0 , 然后连接每个n点 ， 边权为码头的费用 ， 然后跑一边最小生成树。。
太优秀了，在注意一下如果只用到虚拟的点边只有一条的话 ， 就不用加上这个费用；
#include<bits/stdc++.h> using namespace std ; struct no { int u,v,w; }eg[200001]; int fa[100001],val[100001]; bool cmp(no a , no b) { return a.w<b.w; } int find(int u) { if(fa[u]==u)return u; return fa[u]=find(fa[u]); } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1 ; i<=m ; i++) { int a,b,c; scanf("%d%d%d",&eg[i].u , &eg[i].v , &eg[i].w); } for(int i=1 ; i<=n ; i++) { scanf("%d",&val[i]); if(val[i]!=-1) { eg[++m].u=0; eg[m].v=i; eg[m].w=val[i]; } } for(int i=1 ; i<=n ; i++) fa[i]=i; sort(eg+1,eg+1+m,cmp); int ans=0,W=0,IDcost; for(int i=1 ; i<=m ; i++) { int u=eg[i].u , v=eg[i].v , w=eg[i].w; int x=find(u) , y=find(v); if((x!=y) || w<0) { fa[x]=y; ans+=w; if(u==0) { W++; IDcost=w; } } } if(W==1)///只是建一个码头是 ans-=IDcost; printf("%d\n",ans); }
原文：https://www.cnblogs.com/shuaihui520/p/10460045.html