HDU 1863 畅通工程(kruskal算法)

发布时间:2017-1-23 22:49:18 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 1863 畅通工程(kruskal算法)",主要涉及到HDU 1863 畅通工程(kruskal算法)方面的内容,对于HDU 1863 畅通工程(kruskal算法)感兴趣的同学可以参考一下。

转载请注明出处:http://blog.csdn.net/a1dark 分析:还是一道水水的最小生成树、改了一点条件而已、代码基本不变、继续水、 增加要点:kruskal是以边来贪心、然后用并查集查询当前边的两个点是否已经用过、查询的时候并查集用到了路径压缩、可以节省下次查询时间、 #include<stdio.h> #include<algorithm> using namespace std; struct node{ int s,e; int val; }flag[150]; int map[150]; int n,m,temp; int cmp(node a,node b){ if(a.val<b.val) return 1; else return 0; } void init(){ for(int i=1;i<=m;i++) map[i]=i; } int find(int x){ int r=x; while(r!=map[r]) r=map[r]; int b=x; int f; while(b!=r){ f=map[b]; map[b]=r; b=f; } return r; } int merge(int x,int y){ int fx=find(x); int fy=find(y); if(fx!=fy){ map[fx]=fy; temp--; return 1; } return 0; } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ if(n==0)break; for(int i=0;i<n;i++){ scanf("%d%d%d",&flag[i].s,&flag[i].e,&flag[i].val); } sort(flag,flag+n,cmp); int sum=0,ans=0; temp=m-1; init(); for(int i=0;i<n;i++){ ans=merge(flag[i].s,flag[i].e); if(ans) sum+=flag[i].val; } if(temp>0) printf("?\n"); else printf("%d\n",sum); } return 0; }

上一篇:【转】iOS开源项目汇总
下一篇:Java:对象的强、软、弱和虚引用

相关文章

相关评论