nyoj38(最小生成树）

本文主要是介绍nyoj38(最小生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

布线问题

描述

南阳理工学院要进行用电线路改造，现在校长要求设计师设计出一种布线方式，该布线方式需要满足以下条件：
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

解题思路：其实很简单，这题就是考无向图的无环最小生成树，求最短的路径；

代码如下：我用的是Kruskal算法，用prim算法一样的也可以解决问题

#include<iostream>
#include<stioh>
#include<algorithm>
using namespace std;
#define M 250005 //最多边数
#define N 505 //最多顶点数
typedef struct edge
{int a;int b;int value;
}edge;
edge edges[M];
int final[N],num1[N];            //存储父节点 
int nodecount[N];        //存储该节点孩子结点的个数 
bool cmp(edge a,edge b)
{return a.value<b.value;
}
int findp(int n)            //寻找父节点 
{if(final[n]==n)return n;elsefinal[n]=findp(final[n]);return final[n];
}
bool Union(int x,int y)          //合并 
{int rootx=findp(x);int rooty=findp(y);if(rootx==rooty)return false;else if(nodecount[rootx]<=nodecount[rooty]){final[rootx]=rooty;nodecount[rooty]+=nodecount[rootx];}else{final[rooty]=rootx;nodecount[rootx]+=nodecount[rooty];}return true;
}
int main ()
{//freopen("1.txt","r",stdin);int num=0;int n,m,sum,k;int i;cin>>k;while (k-- ){scanf ( "%d%d", &n, &m );num=0;              //记录生成树中的边的数目 sum=0;for(i=1;i<=m;i++){scanf("%d%d%d",&edges[i].a,&edges[i].b,&edges[i].value);}for(i=1;i<=n;i++)cin>>num1[i];for(i=1;i<=n;i++)      //初始化                {final[i]=i;nodecount[i]=1;}sort(edges+1,edges+m+1,cmp);   //排序                             for(i=1;i<=m;i++)              //遍历所有的边 {if(Union(edges[i].a,edges[i].b))         //合并 {num++;//记录最小生成树的边数sum+=edges[i].value;//printf("%d->%d\n",edges[i].a,edges[i].b);}if(num==n-1)               //找到了最小生成树 break;}sort(num1+1,num1+n+1);printf("%d\n",sum+num1[1]);}return 0;
}
//kruskal算法模板

这篇关于nyoj38(最小生成树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---