10126人阅读
声明:这篇博客仅用于(zhang)交(fang)流(wen)学(liang)习，让大家更快的熟悉赛题，不会涉及到具体的算法细节，所以不会影响到前排同学的排名，请不用担心。
有一个无向网络，网路的每条路径有一个带宽容量限制和单位带宽的花费，网路中有一些消费节点，每个消费节点有一个容量需求，现在让你在网络中布置一些服务器给消费节点提供带宽，每个服务器有固定的费用，让你设计一种服务器的布置方案使得费用尽量少并输出服务器给消费节点提供带宽的路径
这道题是一道NP-hard问题，可以归为优化选址一类的问题中去。
对于确定服务器的位置这道题就是一个经典的多源多汇费用流问题了，多于多源多汇的费用流问题可以参考我的另一篇博客：
这里简单说一下思路：建立一个超级源点(不是图中的点，自己虚拟的)连接到所有的服务器，再建一个超级汇点连接到所有消费节点，这样就变成了一个单源点单汇点的费用流问题，而费用流的求解可以用SPFA、dinic算法、单纯性算法等，但是做为一个经典的算法，我认为SPFA就差不多足够了(其实是比较懒只会这一个算法)。
由于题目要求还要输出路径，所以在费用流求完之后需要再进行一次深广搜找路径。
而对于这道题主要就是服务器位置的确定了。主流的解决思路有遗传算法、模拟退火、粒子群等。
模拟退火类似于爬山，大体思路是选取一个初始状态，从这个状态开始走，每次去找一个临近地状态，如果比当前的解好就走它，比当前的差有一定的概率会走它，在模拟退火里面这个概率是用温度作为一个影响因子来表示的，温度越小，走差解的可能性越小。随着迭代次数温度逐渐降低最终收敛到一个局部最优值。
而遗传算法则是随机选一些状态作为初始的个体构成一个群体，每一次迭代都将这个群体中解较优的个体进行叫交叉互换和变异之后形成新的解。但是使用遗传算法需要我们认同一个假设:两个较优解通过交叉互换变异之后也得到较优解的可能性是比较大的。
粒子群可以看成是让一群粒子在整个搜索空间搜索，这样可以比较好的避免陷入局部最优，但同时由于粒子数很多使得迭代一次所花费的时间也相对较多。
以上几个算法本质上都是启发式搜索，目的都是高效地找到较优的解，各有各的好处，效果还是要具体实验之后才能知道
这些启发式搜索的效果和参数有很大关系，算法设计好了之后的调参工作也是很重要的，参数调不好最后都退化成了xjbs(话说这次比赛xjbs算法又火了一把233)
我认为华为软件精英挑战赛是一个很锻炼学生能力的比赛，不论是对编程能力、查阅文献能力还是实验能力都是很大的锻炼。
去年止步于区域前64，希望今年能冲进32！
晒一下目前排名(现在小数据的测试仅做娱乐使用，实际还是要等到大数据出来之后排名才有参考价值):
3/25排名更新(经过了不断的优化之后还是有惊无险地保住了前3)：
最后推荐两个复杂网络分析工具：
小数据看起来是这样的：
然而数据大了之后就变这样了:
(Updating。。。)
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：50439次
积分：1989
积分：1989
排名：第19752名
原创：149篇
评论：140条
(13)(1)(2)(5)(1)(12)(42)(2)(12)(16)(2)(11)(32)(3)(1)(1)后使用快捷导航没有帐号？
平板/笔记本
云服务专区
2015华为软件精英挑战赛赛题正式发布，看了你就明白怎么...
&花粉俱乐部团队&
来自：浏览器
2015华为软件精英挑战赛正式启动
头奖 20万等你赢，总奖池 100 万，还不来看看？！
& && &&&2015华为软件精英挑战赛于4月29日正式启动！请登录大赛官网：获取详细信息。& && &&&2015华为软件精英挑战赛（2015 HuaweiSoftware Elite Challenge）是华为公司面向全国高校学生举办的大型软件竞赛，致力于让参赛学生充分感受软件设计和写好代码的魅力，验证用软件设计和编程解决问题的能力，并通过比赛增强实战实践和与人沟通、协作的能力。& && & 本次大赛口号“万码奔腾战江湖”，将在全国设8个赛区同时开展。大赛分区域线上初赛、区域现场复赛和全国总决赛共三轮，选手采用组队方式（1-3人）参赛。本次大赛赛题于5月5日正式发布，题型将充满乐趣和挑战，我们期待和你共同感受coding的魔力。
线上页面-小v2_副本.jpg (49.7 KB, 下载次数: 204)
17:29 上传
一、参赛人员& && & 只要你是& && & 1、全日制在校大学生（本、硕）& && & 2、喜爱写软件，满怀激情与梦想& && & 3、对自己和小伙伴有足够的信心你就可以参与大赛报名！& && & 你可以选择单枪匹马闯大赛（1人参赛），也可以选择强强联手（2人或3人组队参赛，可跨校组队，以组长所在学校所属区域作为参赛区域），英雄不问出处，竞技场上见分晓。
二、奖项设置全国总决赛：& && & 至尊天下奖（一等奖），1队，20万现金大奖& && & 笑傲江湖奖（二等奖），2队，10万现金大奖& && & 蟾宫折桂奖（三等奖），5队，5万现金大奖区域现场复赛：& && & 每区域前4名队伍获雄霸一方奖，晋级全国总决赛，并获得华为最新款手机，加入优才计划区域线上初赛：& && & 1、每区域前32名队伍获横扫千军奖，晋级本区域现场复赛，获得晋级奖品和证书& && & 2、每区域前64名队伍获得独一无二的精美纪念品
三、赛程设置& && & 4月底& && &启动报名& && & 5月5日& & 赛题发布& && & 5月& && && &区域线上初赛& && & 6月& && && &区域现场复赛& && & 6月底或7月上旬& &全国总决赛& && & 具体日期以正式通知为准，大赛组委会对赛事日程保留最后解释权
四、优才计划& && & 1、面试绿卡：免技术面，通过终面后给予高薪Special Offer& && & 2、应届生实习直通车：国内实习机会任选、岗位工作地任选& && & 3、精英导师贴身辅导：配备首席技术专家和人力资源主管进行一对一的技术指导和职业生涯指导& && & 4、职业快车道：入职后高级主管、首席技术专家担任导师，有机会进入专家或管理者梯队培养计划
2015华为软件精英挑战赛赛题正式发布，看了你就明白怎么去赢20万啦
& && & 万码奔腾战江湖，如何战？看过来！比的不仅仅是软件架构、代码设计，更是跟对手的博弈和较量。怎么虐题，怎么虐人，看你的了！
赛题说明.jpg (314.04 KB, 下载次数: 214)
09:19 上传
& && & 更多信息请登录本次
& && & #华为软件精英挑战赛#让你幸福感爆棚的东西来了！德州扑克比赛demo视频，本次大赛命题组出品，极简，极明了，堪称德州扑克速成宝典，爸爸妈妈再也不用担心我看不懂赛题了。
width:100%">
&禁止发言&
来自：浏览器
提示: 作者被禁止或删除 内容自动屏蔽
width:100%">
&禁止发言&
来自：浏览器
提示: 作者被禁止或删除 内容自动屏蔽
width:100%">
&独步江湖&
来自：浏览器
怎么报名？
width:100%">
&禁止发言&
来自：浏览器
提示: 作者被禁止或删除 内容自动屏蔽
width:100%">
&独步江湖&
来自：浏览器
我是一个人还行？已经毕业了
目前只能接受在校学生，很抱歉，不过还是欢迎关注比赛进程哟
width:100%">
&禁止发言&
来自：浏览器
提示: 作者被禁止或删除 内容自动屏蔽
width:100%">
&独步江湖&
来自：浏览器
width:100%">
&炉火纯青&
来自：浏览器
支持！！！！
width:100%">
&新学乍练&
来自：浏览器
软件比赛为啥不能报名呀？有省份学校限制还是怎么的？
width:100%">
在职斑竹的身份勋章，感谢斑竹的辛勤劳动
1000万花粉
纪念花粉俱乐部注册花粉数超过1000万
相亲角人文随拍青岛之旅河北白石山细看世界鸣沙山随手拍大观公园之夏
花粉客户端
Make it Possible
Make your device special
华为云服务
Huawei cloud services
音乐播放器
Huawei Music
Huawei Vmall
更新了自己的基本资料
更新了自己的基本资料
更新了自己的基本资料
成为了好友
成为了好友
关注花粉俱乐部
联系我们：
|关注花粉俱乐部：
Copyright (C)
华为软件技术有限公司 版权所有 保留一切权利2017年华为性格测试题(题库+攻略)_财会/金融考试_资格考试/认证_教育专区。...乐意去适应新的挑战 工作繁忙时,仍然能把事情处理得很好 良好的书面沟通能力 ...
2017销售精英挑战赛杭厦赛区决赛试题_生产/经营管理_经管营销_专业资料。此为华为21017年销售精英挑战赛杭夏赛区决赛试题,有意参加此比赛或希望加入华为成为客户经理...
2014年第四届“华为杯”南邮大学生程序设计竞赛【选拔赛】题目_计算机软件及应用...但是不能充分展示南邮作为中国 IT 精英摇 篮的风采,建议 2014 年 PK 赛演唱...
华为2014 年机试题 1 //华为 2014 年机试题 1:输入 1--50 个数字,求出最小数和最大数的和 //输入以逗号隔开 #include&stdio.h& #define N 50 void ...
华为新员工转正笔试题(附答案) 【第一部分 行政篇】 1、华为公司的全称为() A、深圳市华为技术有限公司 B、华为技术有限公司 C、华为公司 D、我司 (答案:B...
这道题目和华为主题未来网络有何关系,或者说题目背景 保留一点神秘感,待到开幕...@软件 精英挑战赛命题组专家–吴迪 你可以把 10s 分成 10 个 1s 82、 有解...
华为2014机试题目与答案_IT认证_资格考试/认证_教育专区。华为 2014 机试题目与答案华为 2014 校园招聘的机试题目和 2013 年的完全一样。 一、题目描述(60 分...
选择题:(每题 2 分,共 100 分) 1、以下属于物理层的设备是( ) 14 / 90 华为笔试题大全 ; A、中继器 B、以太网交换机 C、桥 D、网关 2、在以太网...
(这种方法在这题是错的,求出的只是一种路径,但不一定是最短,放在这仅为练...南邮华为俱 乐部会长小郑同学最近计划进入股市淘金,看中一支股票,借本次华为赛...
[find++]; } 华为最后三个大题 1.A,B,C,D 四个进程,A 向 buf 里面写数据,B,C,D 向 buf 里面读数据, 当 A 写完,且 B,C,D 都读...如何评价2016华为软件精英挑战赛？ - 知乎516被浏览40225分享邀请回答354 条评论分享收藏感谢收起3314 条评论分享收藏感谢收起查看更多回答7 个回答被折叠（）}