【MST+虚拟节点+Kruskal】swjtuOJ 2093

【注：交大的看到这篇文章要学会自己写，不要为了比赛而比赛！~】

题目大意

给你n个节点和n个节点的权值，，m条连接边，求连通权值的最小和(MST) n <= 10^5

最小生成树问题，注意原图不一定连通，构造虚拟节点0,0到其他节点边权值赋值为节点权值，求增加2n条边之后的MST即可，注意多加n个节点，数组要开成原来的两倍，笔者RE了一次QAQ~

–

说一下思路构造虚拟节点很好解决了点权值的问题，保证了图的连通性节点n比较大,图用邻接表存储，MST采用Kruskal算法，时间慢了一点

邻接表要开成2倍存放虚拟节点对应的边

参考代码;const int _max = 2e5 + 10;int n,m,u,v,w,cost[_max];struct Edge{ int u,v,w;}edge[_max];tol;//边数，加边前赋值为0void addedge(int u,int v,int w){ edge[tol].u = u; edge[tol].v = v; edge[tol++].w = w;}//排序函数，将边按照权值从小到大排序bool cmp(Edge a,Edge b){ return a.w < b.w;}int find(int x){ if(F[x]==-1) return x; else return F[x] = find(F[x]);}//传入点数,返回最小生成树的权值ll Kruskal(int n){ clr(F,-1); sort(edge,edge+tol,cmp); int cnt = 0;//计算加入的边数 ll ans = 0; for(int i = 0; i < tol; ++ i){int u = edge[i].u;int v = edge[i].v;int w = edge[i].w;int t1 = find(u);int t2 = find(v);if(t1 != t2){ans += w;F[t1] = t2;cnt ++;}if(cnt == n – 1) break; } if(cnt < n – 1) return -1; else return ans;}int main(){ #ifndef ONLINE_JUDGE freopen(“input.txt”,”r”,stdin); #endif // ONLINE_JUDGE while(scanf(“%d%d”,&n,&m)==2){for(int i = 1; i <= n; ++ i) scanf(“%d”,cost+i);tol = 0;for(int i = 0; i < m; ++ i){scanf(“%d%d%d”,&u,&v,&w);addedge(u,v,w);}for(int i = 1; i <= n; ++ i)//构造虚拟节点，处理不连通的问题addedge(0,i,cost[i]);printf(“%lld\n”,Kruskal(n+1)); } return 0;}

近朱者赤，近墨者黑

相关文章：

你感兴趣的文章：

标签云：