免费预览已结束,剩余1页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
#include#include#include#includeusing namespace std;#define INF 99999999#define min( a, b ) ( (a) (b)?(a): (b) )struct point double x; double y;p200;int pre200;/记录该节点的前驱double graph200200, ans;/图数组和结果bool visit110, circle110;/visit记录该点有没有被访问过,circle记录改点是不是在一个圈里int n, m, root;/顶点数+边数+根节点标号void dfs( int t )/一个深度优先搜索,搜索出一个最大的联通空间 int i; visitt= true; for(i= 1; i= n; +i ) if( !visiti & graphti!= INF ) dfs( i ); bool check()/这个函数用来检查最小树形图是否存在,即如果存在,那么一遍dfs后,应该可以遍历到所有的节点 memset( visit, false, sizeof(visit) ); dfs( root ); for( int i= 1; i= n; +i ) if( !visiti ) return false; return true;double dist( int i, int j ) return sqrt( (pi.x-pj.x)*(pi.x-pj.x)+(pi.y-pj.y)*(pi.y-pj.y) );int exist_circle()/判断图中是不是存在有向圈 int i; int j; root= 1; preroot= root; for(i= 1; i= n; +i ) if( !circlei & i!= root ) prei= i; graphii= INF; for(j= 1; j= n; +j ) if( !circlej & graphji graphpreii )/找出指向i最小的 prei= j; /这个for循环负责找出所有非根节点的前驱节点 for( i= 1; i= n; +i ) if( circlei ) continue; memset( visit, false, sizeof(visit) ); int j= i; while( !visitj ) visitj= true; j= prej; if( j= root ) continue; return j; /找圈过程,最后返回值是圈中的一个点 return -1;/如果没有圈,返回-1void update( int t )/缩圈之后更新数据 int i; int j; ans+= graphprett; for(i=pret; i!= t; i= prei ) ans+= graphpreii; circlei= true; /首先把圈里的边权全部加起来,并且留出t节点,作为外部接口 for(i= 1; i= n; +i ) if( !circlei & graphit!= INF ) graphit-= graphprett; /上面这个for循环的作用是对t节点做更新操作,为什么要单独做?你可以看看线面这个循环的跳出条件。 for(j= pret; j!= t; j= prej ) for( int i= 1; i= n; +i ) if( circlei ) continue; if( graphij!= INF ) graphit= min( graphit, graphij- graphprejj ); graphti= min( graphji, graphti ); /这个循环对圈中的其他顶点进行更新void solve() int j; memset( circle, false, sizeof(circle) ); while( ( j= exist_circle() )!= -1 ) update( j ); for( j= 1; j= n; +j ) if( j!= root & !circlej ) ans+= graphprejj; printf(%.2lfn, ans );int main() int i; while( scanf(%d%d,&n,&m)!= EOF ) for(i= 0; i= n; +i ) for( int j= 0; j= n; +j ) graphij= INF; for(i= 1; i= n; +i ) scanf(%lf%lf,&pi.x, &pi.y ); for(i= 0; i m; +i ) int a, b; scanf(%d%d,&a,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024届北京西城师大附中七下英语期末经典模拟试题含答案
- 2024年新型复合型菌剂项目发展计划
- 2024年口腔溃疡含片合作协议书
- 2024年触变剂合作协议书
- 2024年噪声频谱分析仪合作协议书
- 2024年LED灯具项目建议书
- 2024年铁路旅客运输服务项目发展计划
- 2024届安徽省潜山市英语八年级第二学期期末质量跟踪监视模拟试题含答案
- 2024届安徽省蚌埠市英语八下期末达标检测模拟试题含答案
- 2024广告安装合同范本
- 肾小管酸中毒护理查房
- 收纳盒注塑模具设计(论文-任务书-开题报告-图纸)
- 山药粉项目经营分析报告
- 2024届山东济宁任城区中考四模数学试题含解析
- CONSORT2010流程图(FlowDiagram)【模板】文档
- 2024届高考地理冲刺复习 新疆特色农业-水产养殖业
- 电动汽车动力电池技术智慧树知到课后章节答案2023年下深圳职业技术学院
- 顾问式销售的有效技巧
- 用好乡土文化 做好小学德育获奖科研报告
- 阻车桩施工方案
- 《好习惯伴我成长》小学生学习习惯培养家长会课件
评论
0/150
提交评论