管道铺设施工的最佳方案-贪心算法

/*需要在某个城市的n个居民区之间铺设煤气管道，则在这n个居民区之间只要铺设n-1条管道即可。假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同。选择最优的施工方案能使总投资尽可能少，这个问题即为求网的“最小生成树”问题。参照以下居民区示意图，使得求解算法为：在可能架设的n条管道中选取n-1条，既能连通n-1个居民区，有使总投资达到“最小”。网可采用邻接矩阵为存储结构，以定点对（i,j）的形式输出最小生成树的边。要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。*///=======================================================================================================//功能：最小生成树的两种算法#includeiostream.h//c++输入和输出等如cout#includeconio.h//c输入和输出等如getch#includewindows.h//窗口类操作，系统调用如清屏等#includestring.h//字符串操作#includefstream.h//文件读写操作#includeiomanip.h//控制输出流格式enumreturninfo{success,wrong,fail,error};//定义错误类型清constintMaxsize=20;//设置邻接矩阵的最大限【任意设置】floatMGraph[Maxsize][Maxsize]={0};//邻接矩阵初始化为0intflag[Maxsize]={0};//初始化标志位的信息全部为0intFlag[Maxsize]={0};//初始化已经删除的结点的信息标志位为0intNum=10,num=0;//每次处理一批具体数据中结点的个数classtreatment;//treatment类的申明classinterfacebase;//interfacebase类的申明//////////////////////////////////////////////////////////////////////////////////////开始图形界面constchar*begin_file[]={,//1╭─────┬┬┐┌┬┐┌┬┐┌┬┐┌┬┐┌┬┐┌┬┐┌┬┬────╮,//2│├贪┤├心┤├★┤├最┤├小┤├生┤├成┤├树┤│,//3├─────┴┴┘└┴┘└┴┘└┴┘└┴┘└┴┘└┴┘└┴┴────┤,//4│★☆★管道铺设施工最佳方案★☆★│,//5├─────────────────────────────────┤,//6││,//7│☆功能介绍：│,//8│1.文件读写操作│,//9│2.对边和点的信息可以进行增加、删除和修改操作。│,//10│3.及时将系统中的残余结点空间释放。│,//13│4.数据的输入有两种方式：文件读取和从键盘输入。│,//14│5.显示当前邻接矩阵的情况。│,//15│6.正确返回边处理中产生的信息。│,//17│7.两种最小生成树的算法：Kruskal和Pram。│,//18│8.数据输入不分大小写。│,//19├─────────────────────────────────┤,//20│╱◥██◣¤╭⌒╮╭⌒╮│,//21│︱田︱田田|╰-----------------时间：二○一○年十月------│,//22│╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬│,//23╰─────────────────────────────────╯,//24};/*开始界面函数*/voidbegin_face(){for(intj=0;j21;j++){coutsetw(5)begin_file[j]endl;Sleep(50);}coutendl阅读完毕，请按任意键继续.......endl;}////////////////////////////////////////////////////////////////////////////////////classnode//创建一个node类来表示边的信息{public:node(charinitpoint1,charinitpoint2,floatinitweight,node*initnext=NULL);//node(node*initnext=NULL);//【构造函数重载，为头结点节省空间】~node();//voiddisplay(void);//显示边的结点以及权值信息charpoint1;//边的起点【约定ASCII码小的点】charpoint2;//边的终点【约定ASCII码大的点】floatweight;//边的权值node*next;//后继结点指针};node::node(charinitpoint1,charinitpoint2,floatinitweight,node*initnext){point1=initpoint1;point2=initpoint2;weight=initweight;next=initnext;}node::node(node*initnext){next=initnext;}node::~node(){}voidnode::display(void){coutpoint1point2=weightendl;}//////////////////////////////////////////////////////////////////////////////classlinklist//定义链表linklist类{friendclassinterfacebase;friendclasstreatment;private:node*headp;intnumber;//统计每个链表中结点的个数public:linklist();//构造函数~linklist();//析构函数voidclearlist(void);//清空链表boolempty(void)const;//判断是否空链};linklist::linklist()//构造函数{headp=newnode;//申请新结点，作为头结点headp-next=NULL;//头结点的地址域预设为空地址number=0;//计数器清零，表明开始时没有实际数据}linklist::~linklist()//析构函数{clearlist();//删除所有数据，释放所有结点deleteheadp;//把头结点也释放掉number=0;//计数器清零，表明开始时没有实际数据}voidlinklist::clearlist(void)//清空链表{node*searchp=headp-next,*followp=headp;//初始化两个指针while(searchp!=NULL){followp=searchp;searchp=searchp-next;deletefollowp;}headp-next=NULL;//保留了最后一个结点，就是头结点，并且链域置为空number=0;//计数器也清零}boollinklist::empty(void)const//是否空链{if(number==0)returntrue;elsereturnfalse;}//////////////////////////////////////////////////////////////////////////////classtreatment//定义一个处理操作类treatment{public:treatment();~treatment();voidtraveral(void);//显示当前时期的临界矩阵的信息voidfailflag(void);//显示标志位置的信息returninfonodework(void);//结点信息的增删操作returninfoedgework(void);//边的信息增删操作returninfomodedge(void);//修改边的权值信息boolread();//读文件操作charininfo(chariname);//处理输入字母信息（如果小写换大写）returninfokruskall();//Kruskall算法returninfoprim();//Prim算法protected:linklistlist[4];//[0]、[1]表示Kruskall算法的初始和最终数据,[2]、[3]表示Prim算法的初始和最终数据};treatment::treatment(){}treatment::~treatment(){}voidtreatment::traveral(void){inti,j;charinode='A';cout┃;for(i=0;iNum;i++)coutsetw(6)setiosflags(ios::right)inode++;inode='A';//重新赋值coutendl━━╋;for(i=0;iNum;i++)cout━━━;for(i=0;iNum;i++){coutendlsetw(2)inode++┃;for(j=0;jNum;j++){if(Flag[i]==1||Flag[j]==1)//删除点coutsetw(6)setiosflags(ios::right)▅;elseif(i!=j&&MGraph[i][j]==0)//无边coutsetw(6)setiosflags(ios::right)∞;elsecoutsetw(6)setiosflags(ios::right)MGraph[i][j];}coutendl┃;}coutendlendl【温馨提示!】数据显示为▅的表示该点被删除，无数据显示。endlendl;}returninfotreatment::nodework(void)//结点信息的增删操作{charinode;introw,col,ch;cout1、增加结点操作endl2、删除结点操作endl3、退出endl请选择：;cinch;if(ch==1){cout您可以选择的新增结点有：;Flag[Num]=1;Num++;for(row=0;rowNum;row++)if(Flag[row]==1)coutsetw(5)char(row+'A');coutendlendl请选择：;cininode;inode=ininfo(inode);//输入数据检测if(inode==0)//输入数据有错returnerror;if(Flag[inode-'A']!=1)//没有输入正确returnerror;Num--;Flag[Num]=0;//重新回到0if(inode-'A'==Num){Num++;num++;}//如果新增结点为后续点则Num++Flag[inode-'A']=0;//赋值0num--;}elseif(ch==2){cout您可以选择的删除结点有：;for(row=0;rowNum;row++)if(Flag[row]==0)coutsetw(5)char(row+'A');coutendlendl请选择：;cininode;inode=ininfo(inode);//输入数据检测if(inode==0)//输入数据有错returnerror;if(Flag[inode-'A']==1)//没有输入正确returnerror;num++;//被删结点数num++Flag[ino