pirm算法最小生成树题目是N台电脑,求每个相连,输入矩阵啊a【i】【j】表示i和j连接所需费用我是用个递增序列,求每增加个点后待连接的最小边.#include#includeint r=0队列右端点,l=1左端点,dui[10001]队列,pos[10001]队列里对应的实际电脑编号,i,j,n,a[101][101],q[101]判断着个点是否已经被连过,ans=0答案;void cha(int x,int y)将新边插入到队列里,维护单调{int i;for(i=r;i>=l-1;i--){if(i
2019-05-30
pirm算法最小生成树
题目是N台电脑,求每个相连,输入矩阵啊a【i】【j】表示i和j连接所需费用
我是用个递增序列,求每增加个点后待连接的最小边.
#include
#include
int r=0队列右端点,l=1左端点,dui[10001]队列,pos[10001]队列里对应的实际电脑编号,i,j,n,a[101][101],q[101]判断着个点是否已经被连过,ans=0答案;
void cha(int x,int y)将新边插入到队列里,维护单调
{
int i;
for(i=r;i>=l-1;i--)
{
if(i==l-1){dui[i+1]=x;pos[i+1]=y;break;}
if(dui[i]>x){dui[i+1]=dui[i];pos[i+1]=pos[i];}
else {dui[i+1]=x;pos[i+1]=y;break;}
}
}
int pai(int x){
int j;
for(j=1;j
优质解答
你要实现还是要解释?
要解释的话,简而言之就是贪心选择某初始点集的最短邻边n-1条,同时避免构成环.
要实现到处都是,比如下面一段C描述：
/*设定一个比较大的整数INF来表示无穷大∞*/
void Prim(int cost[][MAXV],int n,int v)
{ int lowcost[MAXV],min;
int closest[MAXV],i,j,k;
for (i=0;i
你要实现还是要解释?
要解释的话,简而言之就是贪心选择某初始点集的最短邻边n-1条,同时避免构成环.
要实现到处都是,比如下面一段C描述：
/*设定一个比较大的整数INF来表示无穷大∞*/
void Prim(int cost[][MAXV],int n,int v)
{ int lowcost[MAXV],min;
int closest[MAXV],i,j,k;
for (i=0;i