首先，我对这次月赛D题数据出现的一些小失误表示抱歉。D题是一个很经典的搜索题，是对一个noi题目加强后出的。原题为POJ1184，大家可以参考。

这题的经典之处就在于搜索得分成两个部分来完成，首先搜到所有状态的最小步数，然后直接算光标经过的地方经过“Up”,”Down”操作最少需要多少步就行了。说简单点就是只进行部分的搜索。

搜索部分其实就是对所有状态空间的一个遍历，BFS就行了。状态有[2^6][6][6!]种，三个分别是光标扫过的下标，光标所在的下标，和字符串的所有排列。这个明白了题目思路也就很明显了。

原题是在数字间变换，解决方法有几种，不分开考虑各种操作，都还有其他方法可以直接搜过，包括启发式搜索等。加强此题意在突出此解法的经典之处。

这是这次比赛中的一个比较简单的题目。

这个题目的基本思路很简单。首先判断图是否连通，若连通则求最小生成树，看最小生成树的权值是否比题目中限制的权值要小。然后每次去掉图中权值最小的边并求最小生成树，当发现生成树中最大权值和最小权值之差比原来找到的生成树都要小的时候就更新这个差值和生成树的总权值，在最后输出这两个值就是结果。

这个题目中间还是有一些比较容易错的地方的，比如说有些人没有考虑到图是否连通导致WA，有些人没有用到生成树的权值的上限导致TLE。

G: 明显是一个网络流的题目。关键考察对最大流中剩余图的理解。
首先我们来一个简单的问题：
假如网络G的最大流为f,增加网络G中某一条边(a,b,c)的容量，即e(a,b,c)->e(a,b,c+1).那么网络G的最大流如何变化？
很明显，新图的最大流一定为f或者f+1。

如果在原图的剩余图G(f),增加一条边e(a,b,1)后,如果存在增广路，那么新图最大流一定为f+1，否则为f。

结论1：G(f)中增加有向边e(a,b,1)后存在增广路，当且仅G(f)当流可以从s流到a，流可以从b到t。

设G(f)中，设从s出发可以到达的节点集合为A,从某个节点出发可以到达t的节点集合记为B。在G(f)中，A与B的交集为空，这与不存在增广路等价。

结论2：G(f)中增加有向边e(a,b,1)后存在增广路,等价于a属于A且b属于B。

如果新图的最大流变为f+1，我们就把e叫做增加最大流的边。

现在我们回到题目：题目要求统计增加最大流的边的数目。算法就是最大流+搜索+枚举。
(1)求最大流找剩余图G(f)
(2)搜索找G(f)上述A集合和B集合。
(3)枚举所有的边：利用结论2判断是否为增加最大流的边。

另外：注意A集合其实图最小割中，左集合点数最少的最小割。
注意B集合其实图最小割中，右集合点数最少的最小割。

在比赛中，很多人TLE，可能是因为你最大流写得不好(不需要用Dinic，稍微优化的增广路就可以),更多的是后面方法不是最优。很多人第二步就枚举边找增广路(0(n^2))，当然会TLE。

校内队伍只统计个人成绩前六名，对组队参加的队伍不予统计。
第一名：刘绍辉
第二名：吴少良
第三名：张力
第四名：陈建群
第五名：杨晓彬
第六名：满延磊
新人奖：杨晓彬
比赛裁判：
杜鹏
参与出题队员：
陈建群，张力，杜鹏，杨广，满延磊，吴少良，刘绍辉，徐涵。

校外队伍以学校为单位统计，只统计前三名：
第一名：武汉大学
第二名：天津大学
第三名：华东理工大学

1、哈尔滨赛区（哈尔滨工程大学）
网络选拔赛日期：9月20日
现场赛日期：10月11～12

2、北京赛区（北京交通大学）
网络选拔赛日期：9月27日
现场赛日期：10月25～26

OJ: http://acm.bjtu.edu.cn/OnlineJudge/

3、合肥赛区（中国科学技术大学）
网络选拔赛日期：9月28日
现场赛日期：11月15～16

4、杭州赛区（杭州电子科技大学）
网络选拔赛日期：10月18日
现场赛日期：11月22～23

oj:http://acm.hdu.edu.cn/

5、成都赛区（西南民族学院）
网络选拔赛日期：10月19日
现场赛日期：11月29～30

oj:http://acm.hdu.edu.cn/

请各位同学以队为单位，提交自己的队伍信息。
内容包括：

队伍名称：
队长名字：
队员名单：
队伍集训目标：
队伍集训规划：
队员个人集训规划：

请将上述信息发到struggle_lcd@qq.com, 并且抄送chuangxin@mail.hust.edu.cn和iamsempr@gmail.com

如果有好的关于组对赛的建议，也请发到上述邮箱，

–Sempr 修改于2008.07.29 19:27pm

update:

下次不要只发一张图片,尽量多一点文字信息,嗯

谢谢大家支持

by 巫山霏云

    很高兴看到freefcw对网站的调整，这样看起来就舒服多了。

    不过，在这里提一个小小的建议，对所有的作者的，因为现在博客系统被放到的主页的位置，所以大家所发的内容需要把格式调整的合理一些，比如上一篇陈建群同学的题目分析，还是比较建议在编辑器中编辑，最好不要只贴一个链接就完事了，就算贴链接，也最好让链接的长度短一些，实现起来非常容易，传到白云上的文件不要用中文名就好了。话又说回来，最好在日志的内容中提一下文档的信息，毕竟把文档下载下来，再用WORD打开看的成本是蛮高的。

    这些天的个人赛，我也是时不时的关注一下，大家的表现都还是不错的，不过，希望大家不要仅仅把注意力都放到我们自己的OJ上，毕竟这些天，POJ上面还是增加了很多很不错的题目的。

    差不多说完了，大家加油!

http://newhost.byhh.net/f/Algorithm/1216551621/%B8%F6%C8%CB%C8%FCA%CC%E2%B5%C4%C1%ED%D2%BB%BD%E2%B7%A8%BC%B0%C6%E4%BD%E1%C2%DB%B5%C4%CD%C6%B9%E3.doc