普里姆最小生成树算法 南阳38题

思路：这个题目就是从最小生成树，再加上最少的楼连接到外面电缆的花费。

给大家讲解一下普里姆算法：一个点集合 ，一个边集合。初始状态将出发的点加入点集合中，然后把他连接到其他点的边加入到边集合中。然后选出一条最小价值的边。然后在把那个价值最小的边另外的一个顶点加入到点集合中。然后循环下去。直到所有点都加入到点集合中。

布线问题

时间限制： 1000 ms  |  内存限制： 65535 KB 难度： 4 描述 南阳理工学院要进行用电线路改造，现在校长要求设计师设计出一种布线方式，该布线方式需要满足以下条件： 1、把所有的楼都供上电。 2、所用电线花费最少 输入 第一行是一个整数n表示有n组测试数据。(n<5) 每组测试数据的第一行是两个整数v,e. v表示学校里楼的总个数(v<=500) 随后的e行里，每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c<=100)。（哪两栋楼间如果没有指明花费，则表示这两栋楼直接连通需要费用太大或者不可能连通） 随后的1行里，有v个整数,其中第i个数表示从第i号楼接线到外界供电设施所需要的费用。( 0<e<v*(v-1)/2 ) （楼的编号从1开始），由于安全问题，只能选择一个楼连接到外界供电设备。 数据保证至少存在一种方案满足要求。 输出 每组测试数据输出一个正整数,表示铺设满足校长要求的线路的最小花费。 样例输入 1 4 6 1 2 10 2 3 10 3 1 10 1 4 1 2 4 1 3 4 1 1 3 5 6 样例输出 4

代码：

#include<stdio.h> #include<stdio.h> #include<string.h> #include<stdlib.h> #define max 510 #define wqd 65535 typedef struct Graph//整个图的存储 { int map[max][max]; //邻接表 int n;//顶点数目 int e; //边数目 }graph; typedef struct bian//用来保存边价值flag表示这条边有没有被选取访问过。 { int x; int y; int jiazhi; bool flag; }bian; Graph mgraph;int c=0; bool Prim(int v0,int v1,int *d,bian *p)//v0开始的点，v1是楼的花费最小的值 { int k=v1; bool *vis=(bool*)malloc(sizeof(bool)*(mgraph.n+5)); memset(vis,0,sizeof(vis)); d[0]=v0;vis[v0]=1;int sum=0;//累加最小生成树的总价值。 for(int i=0;i<mgraph.n-1;i++)//找第一个点连接的边放入边集合 { for(int j=1;j<=mgraph.n;j++) { if(mgraph.map[d[i]][j]!=0&&!vis[j]) { bian a={d[i],j,mgraph.map[d[i]][j],0}; p[c++]=a; } } int min=99999,u; for(int j=0;j<c;j++)//找边集合中最小价值的边 { if(min>p[j].jiazhi&&!p[j].flag&&!vis[p[j].y]) { min=p[j].jiazhi; u=j; } } d[i+1]=p[u].y;//将最小边另外一端的点加入点集合中 sum+=p[u].jiazhi;//累加价值。 vis[p[u].y]=1; p[u].flag=1; } printf("%d\n",sum+k); } int main() { int n,e,g; scanf("%d",&g); while(g--) { scanf("%d%d",&n,&e);c=0; memset(mgraph.map,0,sizeof(mgraph.map)) ; mgraph.e=e; mgraph.n=n; for(int i=1;i<=e;i++) { int x,y,w; scanf("%d%d%d",&x,&y,&w); mgraph.map[x][y]=w; mgraph.map[y][x]=w; } int *h=(int*)malloc(sizeof(int)*(mgraph.n+5)); int *d=(int*)malloc(sizeof(int)*(mgraph.n+5)); bian *p=(bian*)malloc(sizeof(bian)*(mgraph.e+5)); //prim(1,d,p); for(int i=1;i<=mgraph.n;i++) { scanf("%d",&h[i]); }int min=h[1],u=1; for(int i=2;i<=mgraph.n;i++) { if(min>h[i]){ min=h[i];u=i;} } } }