HDU 1102 Constructing Roads （最小生成树+Kruskal算法入门）

HDU 1102 Constructing Roads （最小生成树+Kruskal算法入门）

【题目链接】：​​click here~~​​

【题目大意】：已知某几条道路已经修完，求全部道路要通路的最小花费

【解题思路】：基础的Kruskal算法了，按照边的权值从小到大排序一遍，符合条件加入到生成树中

代码：

/*Author:HRWkruskal+并查集*/#include using namespace std;const int max_v=105;const int inf=0x3f3f3f3f;int u,v,n,m,a,b;int father[max_v];int find(int x){ if(x==father[x]) return x; return father[x]=find(father[x]);}struct Edge{ int u,v,w;} edge[max_v*max_v];bool cmp(Edge a,Edge b){ return a.w<=b.w;}int kruskal(int n,int m){ sort(edge,edge+m,cmp);//按照边的权值从小到大排序 int x,y; int res=0; for(int i=0; i=j) continue;//!注意 edge[p].u=i; edge[p].v=j; edge[p].w=aa; p++; } init(); scanf("%d",&m); while(m--){ scanf("%d%d",&a,&b); a=find(a); b=find(b); father[b]=a; } printf("%d\n",kruskal(n,p)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。