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

A - Ice_cream’s world III

2024-07-17 06:33:27   221人阅读

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status Practice HDU 2122

Description

ice_cream’s world becomes stronger and stronger; every road is built as undirected. The queen enjoys traveling around her world; the queen’s requirement is like II problem, beautifies the roads, by which there are some ways from every city to the capital. The project’s cost should be as less as better.
 

Input

Every case have two integers N and M (N<=1000, M<=10000) meaning N cities and M roads, the cities numbered 0…N-1, following N lines, each line contain three integers S, T and C, meaning S connected with T have a road will cost C.
 

Output

If Wiskey can’t satisfy the queen’s requirement, you must be output “impossible”, otherwise, print the minimum cost in this project. After every case print one blank.
 

Sample Input

2 1 0 1 10 4 0
 

Sample Output

10 impossible
简单的最小生成树问题，用并查集来做。
 1 #include<cstdio> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 int ans; 6 int father[2000],rank[2000];//父节点，深度记录（这道题没必要用深度记录） 7 //int max1; 8 struct Line{ 9     int first;10     int last;11     int cost;12 }line[50000];//还没学会用数组来记录边，还是在用结构体做的，编程风格有待提高13 int cmp(Line a,Line b){return a.cost<b.cost;}//排序的依据函数14 int find(int x)//找点的父节点，把一条边的点搞到一个集合里面15 {16     if(father[x]!=x)17     {18         father[x]=find(father[x]);//这里有个优化，不会出现长链的情况，直接把father[x]=find[father[x]];19     }20     return father[x];21 }22 bool Union(int a,int b)//合并集合23 {24     int a1=find(a),b1=find(b);25     if(a1==b1) return false;//如果是同一个父亲节点的，return false;26     else{27         father[b1]=a1;//否则合并成一个集合28         ans++;29         rank[a1]+=rank[b1];30         if(max1<rank[a1]) max1=rank[a1];31         return true;32     }33 }34 35 36 int main()37 {38     int a,b,c,n,m;39     while(scanf("%d%d",&n,&m)!=EOF)40     {41         for(int i=0;i<n;i++)42         {43             father[i]=i;44             rank[i]=1;45         }46         for(int i=1;i<=m;i++)47         {48             scanf("%d %d %d",&a,&b,&c);49             line[i].first=a;50             line[i].last=b;51             line[i].cost=c;52 53         }54         sort(line+1,line+m+1,cmp);55         max1=0;56         int sum=0;57         ans=0;58         for(int i=1;i<=m;i++)59         {60             if(Union(line[i].first,line[i].last))61                 sum+=line[i].cost;62         }63         if(ans==n-1) printf("%d\n",sum);64         else printf("impossible\n");65         printf("\n");66     }67     return 0;68 }

 


联系
我们