1 : 第一种 prime 首先确定一个点 作为已经确定的集合 , 然后以这个点为中心 , 向没有被收录的点 , 找最短距离( 到已经确定的点 ) , 找一个已知长度的最小长度的 边 加到 sum里面 然后收录这个点 ,
#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<limits.h> #include<algorithm> #include<queue> #include<vector> #include<set> #include<stack> #include<string> #include<sstream> #include<map> #include<cctype> using namespace std; // prim 针对点 进行 最小生成树的 构造 int a[505][505],visited[505],tem[505],dis,minn,n,m,sum; int main() // 首先 以 1 为 根节点 , 开始向周围寻找 找到一个 最小的边 { // 然后 将 该边的 另一个端点标记为 已访问 然后 将该边 的长度 加到sum 中 int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); sum=0; for(int i=1;i<=n;i++) { tem[i]=INT_MAX; // 除了已经确定 了的楼 , 剩余的楼 到 集合中确定的 距离都是最大 for(int j=1;j<=n;j++) a[i][j]=INT_MAX; // 每两个楼之间的距离超大 } memset(visited,0,sizeof(visited)); while(m--) { int b,c,d; scanf("%d%d%d",&b,&c,&d); a[b][c]=a[c][b]=d; } int n1=n-1,b=0; b=1; // 楼的编号 从1 开始 visited[1]=1; // 1号楼 已经确定 while(n1--) // 只需要确定 n-1 条边 { minn=INT_MAX; for(int i=1;i<=n;i++) { if(b!=i&&a[b][i]<tem[i]&&!visited[i])// 不是自己到自己 { tem[i]=a[b][i]; } } int j; for(int i=1;i<=n;i++) { if(minn>tem[i]&&!visited[i]) { minn=tem[i]; j=i; // 找到和 已知集合相连的 最小的一条边 } } visited[j]=1; b=j; sum+=minn; } minn=INT_MAX; for(int i=0;i<n;i++) { scanf("%d",&b); minn=minn<b?minn:b; // 找到 拉电源 最小花费的 楼 所花费的金额 . } printf("%d ",minn+sum); } return 0; }
2 : kruskal 用一个结构体储存信息 , 然后 根据边长来 排序 , 然后一条一条边的收录 如果 形成了环 就不收录这一条边 .
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<limits.h> 6 #include<algorithm> 7 #include<queue> 8 #include<vector> 9 #include<set> 10 #include<stack> 11 #include<string> 12 #include<sstream> 13 #include<map> 14 #include<cctype> 15 using namespace std; 16 int father[505],sum; 17 struct node 18 { 19 int x,y,l; 20 }; 21 bool cmp(node a,node b) 22 { 23 return a.l<b.l; 24 } 25 int find(int x) // 做了时间上的优化 ,但是 在空间复杂度上比较高 26 { 27 if(x!=father[x]) 28 father[x]=find(father[x]); 29 sum++; 30 return father[x]; 31 } 32 bool merge(int x,int y) // 做了时间复杂度上的优化 让并查集的 深度尽量 浅 33 { 34 int sum1,sum2; 35 sum=0; 36 x=find(x); 37 sum1=sum; // x 的深度 38 sum=0; 39 y=find(y); 40 sum2=sum; // y 的深度 41 if(x!=y) 42 { 43 if(sum1>sum2) 44 father[y]=x; 45 else 46 father[x]=y; 47 return true; 48 } 49 else 50 return false; 51 } 52 node a[125000]; 53 int main() 54 { 55 int t,n,m; 56 scanf("%d",&t); 57 while(t--) 58 { 59 scanf("%d%d",&n,&m); 60 sum=0; 61 for(int i=0;i<m;i++) 62 { 63 int b,c,d; 64 scanf("%d%d%d",&b,&c,&d); 65 a[i].x=b; 66 a[i].y=c; 67 a[i].l=d; 68 } 69 sort(a,a+m,cmp); 70 int count1=0; 71 for(int i=0;i<=505;i++) 72 father[i]=i; 73 int sum1=0; 74 for(int i=0;i<m;i++) // 开始 做了他 75 { 76 if(merge(a[i].x,a[i].y)) // 返回 flase 的话 就代表成环了 77 { 78 count1++; 79 sum1+=a[i].l; 80 if(count1==n-1) // 如果已经形成 树的话 81 break; 82 } 83 } 84 int minn=INT_MAX; 85 for(int i=0;i<n;i++) 86 { 87 int b; 88 scanf("%d",&b); 89 minn=b<minn?b:minn; 90 } 91 printf("%d ",minn+sum1); 92 } 93 return 0; 94 }