本文主要是介绍HDU1233 还是畅通工程+1863 畅通工程【带权并查集】【最小生成树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU1233 还是畅通工程
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int pre[10000];struct node
{int from,to,val;
}p[10000];int cmp(node a,node b)//长度从小到大排序
{return a.val<b.val;
}int find(int x)
{if(x==pre[x])return x;int r=x;while(r!=pre[r])r=pre[r];int i=x,j;while(i!=j){j=pre[i];pre[i]=r;i=j;}return r;
}int main()
{int n,m,i;while(cin>>n && n){m=n*(n-1)/2;int ans=0;memset(p,0,sizeof(p)); for(i=1;i<=n;i++)//初始化 pre[i]=i;for(i=1;i<=m;i++){cin>>p[i].from>>p[i].to>>p[i].val;}sort(p+1,p+1+m,cmp);for(i=1;i<=m;i++){int fx=find(p[i].from);//join int fy=find(p[i].to);if(fx!=fy)//两个村庄没有相连{pre[fx]=fy;//连接起来 ans+=p[i].val;}} cout<<ans<<endl;}return 0;
}HDU 1863 畅通工程
在上一题基础上加了点代码
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int pre[10000];struct node
{int from,to,val;
}p[10000];int cmp(node a,node b)//长度从小到大排序
{return a.val<b.val;
}int find(int x)
{if(x==pre[x])return x;int r=x;while(r!=pre[r])r=pre[r];int i=x,j;while(i!=j){j=pre[i];pre[i]=r;i=j;}return r;
}int main()
{int n,m,i;while(cin>>m>>n && m)//没按题目，我的n是村庄，m是路 {int ans=0,cnt=0;memset(p,0,sizeof(p)); for(i=1;i<=n;i++)//初始化 pre[i]=i;for(i=1;i<=m;i++){cin>>p[i].from>>p[i].to>>p[i].val;}sort(p+1,p+1+m,cmp);for(i=1;i<=m;i++){int fx=find(p[i].from);//join int fy=find(p[i].to);if(fx!=fy)//两个村庄没有路连接{pre[fx]=fy;//连接起来 ans+=p[i].val;cnt++;}} if(cnt==n-1)//边==结点减一 cout<<ans<<endl;elsecout<<"?"<<endl;}return 0;
}
这篇关于HDU1233 还是畅通工程+1863 畅通工程【带权并查集】【最小生成树】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
