- 浏览: 32685 次
最新评论
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 101
struct stuEdge
{
int nFrom;
int nCost;
int nTo;
};
int nInput(stuEdge stuArr[],int nN);
void vSort(int nEdge,stuEdge stuArr[]);
bool bCmp(const stuEdge &stuA,const stuEdge &stuB);
void vMem(int nArr[],int nN);
int nKruskal(int nArr[],stuEdge stuArr[],int nN);
void vCombine(int nN,int nArr[],int nFrom,int nTo);
void vOutput(int nOut);
int main()
{
int nNum;
int nEdgeNum;
int nSet[MAX];
int nAns;
stuEdge stuEdgeArr[MAX*(MAX-1)/2+1];
while(1==scanf("%d",&nNum))
{
nEdgeNum=nInput(stuEdgeArr,nNum);
vSort(nEdgeNum,stuEdgeArr);
vMem(nSet,nNum);
nAns=nKruskal(nSet,stuEdgeArr,nNum);
vOutput(nAns);
}
return 0;
}
int nInput(stuEdge stuArr[],int nN)
{
int i,j;
int nCount;
int nTemp;
nCount=0;
for(i=1;i<=nN;i++)
{
for(j=1;j<=nN;j++)
{
scanf("%d",&nTemp);
if(i<j)
{
nCount++;
stuArr[nCount].nCost=nTemp;
stuArr[nCount].nFrom=i;
stuArr[nCount].nTo=j;
}
}
}
return nCount;
}
void vSort(int nEdge,stuEdge stuArr[])
{
sort(&stuArr[1],&stuArr[nEdge+1],bCmp);
}
bool bCmp(const stuEdge &stuA,const stuEdge &stuB)
{
return (stuA.nCost<stuB.nCost);
}
void vMem(int nArr[],int nN)
{
int i;
for(i=1;i<=nN;i++)
{
nArr[i]=i;
}
}
int nKruskal(int nArr[],stuEdge stuArr[],int nN)
{
int nRet;
int nCount;
int nEdgeInd;
int nF,nT;
nRet=0;
nCount=nN;
nEdgeInd=1;
while(nCount>1)
{
nF=nArr[stuArr[nEdgeInd].nFrom];
nT=nArr[stuArr[nEdgeInd].nTo];
if(nF!=nT)
{
nRet+=stuArr[nEdgeInd].nCost;
nCount--;
vCombine(nN,nArr,nF,nT);
}
nEdgeInd++;
}
return nRet;
}
void vOutput(int nOut)
{
printf("%d\n",nOut);
}
void vCombine(int nN,int nArr[],int nFrom,int nTo)
{
int i;
for(i=1;i<=nN;i++)
{
if(nArr[i]==nTo)
{
nArr[i]=nFrom;
}
}
}
#include<algorithm>
using namespace std;
#define MAX 101
struct stuEdge
{
int nFrom;
int nCost;
int nTo;
};
int nInput(stuEdge stuArr[],int nN);
void vSort(int nEdge,stuEdge stuArr[]);
bool bCmp(const stuEdge &stuA,const stuEdge &stuB);
void vMem(int nArr[],int nN);
int nKruskal(int nArr[],stuEdge stuArr[],int nN);
void vCombine(int nN,int nArr[],int nFrom,int nTo);
void vOutput(int nOut);
int main()
{
int nNum;
int nEdgeNum;
int nSet[MAX];
int nAns;
stuEdge stuEdgeArr[MAX*(MAX-1)/2+1];
while(1==scanf("%d",&nNum))
{
nEdgeNum=nInput(stuEdgeArr,nNum);
vSort(nEdgeNum,stuEdgeArr);
vMem(nSet,nNum);
nAns=nKruskal(nSet,stuEdgeArr,nNum);
vOutput(nAns);
}
return 0;
}
int nInput(stuEdge stuArr[],int nN)
{
int i,j;
int nCount;
int nTemp;
nCount=0;
for(i=1;i<=nN;i++)
{
for(j=1;j<=nN;j++)
{
scanf("%d",&nTemp);
if(i<j)
{
nCount++;
stuArr[nCount].nCost=nTemp;
stuArr[nCount].nFrom=i;
stuArr[nCount].nTo=j;
}
}
}
return nCount;
}
void vSort(int nEdge,stuEdge stuArr[])
{
sort(&stuArr[1],&stuArr[nEdge+1],bCmp);
}
bool bCmp(const stuEdge &stuA,const stuEdge &stuB)
{
return (stuA.nCost<stuB.nCost);
}
void vMem(int nArr[],int nN)
{
int i;
for(i=1;i<=nN;i++)
{
nArr[i]=i;
}
}
int nKruskal(int nArr[],stuEdge stuArr[],int nN)
{
int nRet;
int nCount;
int nEdgeInd;
int nF,nT;
nRet=0;
nCount=nN;
nEdgeInd=1;
while(nCount>1)
{
nF=nArr[stuArr[nEdgeInd].nFrom];
nT=nArr[stuArr[nEdgeInd].nTo];
if(nF!=nT)
{
nRet+=stuArr[nEdgeInd].nCost;
nCount--;
vCombine(nN,nArr,nF,nT);
}
nEdgeInd++;
}
return nRet;
}
void vOutput(int nOut)
{
printf("%d\n",nOut);
}
void vCombine(int nN,int nArr[],int nFrom,int nTo)
{
int i;
for(i=1;i<=nN;i++)
{
if(nArr[i]==nTo)
{
nArr[i]=nFrom;
}
}
}
发表评论
-
最大子段和
2012-01-05 13:59 779给出N个数字, 计算出最大的子段和。 Input 第一行给 ... -
最长不下降子序列长度
2012-01-05 13:55 1309对于序列(1, 7, 3, 5, 9, 4,,有它的一些不下降 ... -
求两字符串匹配的最长子序列
2012-01-05 13:52 1016如果两种特征序列的公共子序列越长表示越接近,现在请你帮助计算出 ... -
编辑距离问题
2012-01-05 13:48 658#include<iostream> #incl ... -
prime
2011-12-01 20:09 612#include<iostream> using ... -
哈弗曼编码
2011-11-28 10:43 1#include<iostream> #defi ... -
哈弗曼编码
2011-11-28 10:42 521#include<iostream> #defi ... -
#贪心算法(零件加工)
2011-10-27 13:25 981#include<stdio.h> #includ ... -
众数问题
2011-10-20 14:57 789#include <stdio.h> #inclu ... -
输油管道问题
2011-10-13 14:45 599#include <stdio.h> #inclu ... -
幂的精确求值
2011-09-22 15:07 461#include<iostream> using ... -
大数加法
2011-09-22 12:56 606#include<iostream> #incl ... -
三姐妹之出题
2011-09-15 14:15 663#include<iostream> #incl ... -
最大子段和问题(分治)(##)
2011-09-08 21:31 665#include<stdio.h> #defin ... -
最大子段和问题(O(N^2))
2011-09-08 15:04 610#include<stdio.h> int a[ ... -
最大子段和问题(O(N^3))
2011-09-08 14:45 476#include<stdio.h> int a[ ...
相关推荐
c++编的kruskal法最小生成树的实现
我自己编写的一个C++ kruskal最小生成树程序,希望可以对初学者有所帮助,错误难以避免,希望大家谅解
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
对给定的图结构,实现求解最小生成树的Kruskal算法。每次在满足和已选边不构成回路的条件下选择一条权植最小的边,添加到新的生成数中。Kruskal算法的实现类似于计算连通枝的算法。它使用了分离集合数据结构以保持数...
该程序是我写的博客“一起talk C栗子吧(第五十回:C语言实例--最小生成树二)”的配套程序,共享给大家使用
以前的作业,为了挣点分,呵呵。 基本都能够运行的,当作作业不错。
Kruskal最小生成树算法实验报告 算法原理 Kruskal算法是贪心法的典例,简单个描述为:给定一组边,将它们按照权重排序,每次挑选权重最小的边做试探,如果
最小生成树的graph形式,易于操作 在界面上画点,划线和输入各线权值,即可生成最小生成树
Kruskal实现最小生成树,其中用并查集判别一条边是否是在同一连通分量中!
prim最小生成树的C++代码,代码长度为95行,使用C++编写
建立一个图,其存储方式采用邻接矩阵形式,利用普里姆算法和克鲁斯卡尔算法求网的最小生成树,按顺序输出生成树中各条边以及它们的权值。
最小生成树kruskal算法 最小生成树kruskal算法
代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树...
Prim算法与Kruskal算法 求最小生成树 源代码 实验报告 完整
第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)算法 第4关求图(邻接表存储)最小生成树的克鲁斯卡尔(Kruskal)算法 稳过 生成树是将图中所有顶点以最少的边连通的子图。权值和最小的生成树就是最小...
数据结构课程设计报告最小生成树Kruskal算法
编程实现Kruskal算法,生成最小代价生成树,其中利用最小堆算法实现。 (随机生成n个点,且随机生成k条边,形成连通图)
通过矩阵输入权值情况,求最小生成树,并按顺序输出每一条路
。