普里姆算法 图论 南阳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//存储边集合 { int x;//边头 int y;//边尾 int jiazhi;//权值 bool flag;//标志这条边有没有被选取 }bian; Graph mgraph;int c=0; bool Prim(int v0,int v1,int *d,bian *p) { 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;//将v0放入点集合中 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;} } // if(mgraph.n==1) printf("%d\n",h[1]); Prim(u,h[u],d,p); } }