kruskal-边的贪心(并查集优化)-3

#include<bits/stdc++.h> using namespace std; const int N=1e4; int f[N+100],siz[N+100]; int c[N+100]; struct node{int u,v,w;}edge[N*20]; bool cmp(node p,node q){return p.w<q.w;} void init(int n){for(int i=0;i<=n;i++) {f[i]=i;siz[i]=1;}} int found(int x) { while(x!=f[x]) { f[x]=f[f[x]]; x=f[x]; } return x; } void Union(int x,int y) { int tx=found(x); int ty=found(y); if(tx==ty) return; if(siz[tx]>siz[ty]){f[ty]=tx;siz[tx]+=siz[ty];} else {f[tx]=ty;siz[ty]+=siz[tx];} } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); int cn=0; for(int i=1,j=m;i<=n;i++) { scanf("%d",&c[i]); if(c[i]!=-1) { edge[j].u=0,edge[j].v=i,edge[j++].w=c[i]; cn++; } } sort(edge,edge+m+cn,cmp); init(n); int cost=0,flag=0,pcost; for(int i=0;i<m+cn;i++) { int x=edge[i].u,y=edge[i].v; int tx=found(x),ty=found(y); if(edge[i].w<=0||tx!=ty) { Union(x,y); if(x==0) { flag++; if(flag==1){pcost=edge[i].w;} } cost+=edge[i].w; } } if(flag==1) cost-=pcost; int flag1=1; for(int i=0;i<=n;i++) if(siz[i]>=n){flag1=0;break;} if(flag1){printf("-1\n");return 0;} printf("%d\n",cost); return 0; }