首页 > 代码库 > HDU - 2122 Ice_cream’s world III

HDU - 2122 Ice_cream’s world III

2024-07-15 01:36:10   220人阅读

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=2122

      最小生成树问题，可采用Kruskal算法，贪心策略，每次选取无向带权图的最短边，并把两端点用

并查集的方式添加到一个集合内。

 1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 const int maxn=1000+5,maxm=10000+10; 5 int u[maxm],v[maxm],w[maxm],r[maxm],p[maxn]; 6 int cmp(const int i,const int j) { return w[i]<w[j];} 7 int find_parent(int x) 8 { 9     if(p[x]==-1)10         return x;11     p[x]=find_parent(p[x]);12     return p[x];13 }14 int main()15 {16     int n,m;17     while(scanf("%d%d",&n,&m)!=EOF){18         for(int i=1;i<=m;i++){19             scanf("%d%d%d",&u[i],&v[i],&w[i]);20             r[i]=i;21         }22         memset(p,-1,sizeof(p[0])*n);23         std::sort(r+1,r+m+1,cmp);24         int anscost=0;25         for(int i=1;i<=m;i++){26             int e=r[i],up=find_parent(u[e]),vp=find_parent(v[e]);27             if(up!=vp){28                 p[vp]=up;29                 anscost+=w[e];30             }31         }32         int flag=0;33         for(int i=0;i<n;i++)34             if(p[i]==-1){35                 flag++;36             }37         if(flag>1)38             printf("impossible\n");39         else40             printf("%d\n",anscost);41         printf("\n");44     }45     return 0;46 }

 


联系
我们