首页 > 代码库 > 最小生成树--->NYOJ-38 布线问题
最小生成树--->NYOJ-38 布线问题
此题是最基础的最小生成树的题目，有两种方法， 一个是prim一个是kruskal算法，前者利用邻接矩阵，后者是利用边集数组
prim算法的思想是：一个点一个点的找， 先找从第一个点到其他点最小的， 把权值存放到一个lowcost的数组中，然后继续找下一个点，然后更新lowcost数组，注意，这时的lowcost不完全是第二个点到所有点的距离，而是，其他点到最小生成树的距离，然后一步一步的求，知道求完所有点
kruskal算法的思想是：先把边集数组按照权值进行排序，之后从最小的往上找，这时有个前提，就是不能有环，这样就能保证最大连通量为1，借助father数组
代码如下：
方法一(Prim):
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 const int MAX = 500 + 10; 6 const int INFINITY = 999999; 7 int map[MAX][MAX]; 8 int Sum; 9 int v, e;//v来存点的个数，e来存边的个数 10 void mini_span_tree_prim()11 {12 int lowcost[MAX];13 lowcost[1] = 0;//标记已经加到最小生成树中 14 for(int i = 2; i <= v; i++)15 {16 lowcost[i] = map[1][i];17 }18 for(int i = 2; i <= v; i++)19 {20 int j = 2;21 int index = 1;22 int minweight = INFINITY;23 while(j <= v)24 {//找出最小的边来，并保存其坐标 25 if(lowcost[j] != 0 && lowcost[j] < minweight)26 {27 minweight = lowcost[j];28 index = j;29 }30 j++;31 }32 lowcost[index] = 0;//标记已经加到最小生成树中 33 Sum += minweight;34 for(j = 2; j <= v; j++)35 {//判断没有加到最小生成树中的和比当前权值要小的点 36 if(lowcost[j] != 0 && lowcost[j] > map[index][j])37 {38 lowcost[j] = map[index][j];39 }40 }41 }42 }43 int main()44 {45 //freopen("1.txt", "r", stdin);46 int n;47 scanf("%d", &n);48 while(n--)49 {50 Sum = 0;51 scanf("%d %d", &v, &e);52 int t1, t2, t3;53 memset(map, 1, sizeof(map));54 for(int i = 1; i <= v; i++)55 {56 map[i][i] = 0;57 }58 for(int i= 0; i < e; i++)59 {60 scanf("%d %d %d", &t1, &t2, &t3);61 map[t1][t2] = t3;62 map[t2][t1] = t3;63 }64 int mincost = INFINITY;65 for(int i = 0; i < v; i++)66 {67 scanf("%d", &t1);68 mincost = min(mincost, t1);69 }70 mini_span_tree_prim();71 printf("%d\n", Sum + mincost);72 } 73 return 0;74 }
方法二(Kruskal):
#include <stdio.h>#include <algorithm>#include <cstring>using namespace std;typedef struct Node{ int s; int e; int weight;}Node;const int MAX = 500 + 10;const int INFINITY = 99999999;Node arr[MAX * 250];int father[MAX];int sum;int v, edges;bool cmp(Node a, Node b){ return a.weight < b.weight;}int find(int f){ while(father[f] > 0) f = father[f]; return f;}//生成最小生成树 void mini_span_tree_kruskai(){ int n, m; int cnt = 0; for(int i= 0; i < edges; i++) { n = find(arr[i].s); m = find(arr[i].e); if(cnt == v - 1)//优化，如果找到了n-1条边，这时退出就行了 break; if(n != m)//判断是否构成了环 { father[m] = n; sum += arr[i].weight; cnt++; } }}int main(){ int n; scanf("%d", &n); while(n--) { memset(arr, 0, sizeof(arr)); memset(father, 0, sizeof(father)); sum = 0; scanf("%d %d", &v, &edges); for(int i = 0; i < edges; ++i) { scanf("%d %d %d", &arr[i].s, &arr[i].e, &arr[i].weight); } int mincost = INFINITY; int t; for(int i = 1; i <= v; i++) { scanf("%d", &t); mincost = min(mincost, t); } sort(arr, arr + edges, cmp);//排序 // for(int i = 0; i < edges; i++)// printf("%d %d %d\n", arr[i].s, arr[i].e, arr[i].weight);// printf("%d\n", mincost); mini_span_tree_kruskai(); printf("%d\n", sum + mincost); } return 0;}
最小生成树--->NYOJ-38 布线问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。