18 Apr 10 武汉大学第八届程序设计竞赛部分决赛题目分析

在这里简单说一些我出的题目。

F: Pie

此题很明显的是一个最小匹配的模型。而后根据题目数据的特点可以利用DP来解决。

简单说一下性质：

1. 排序之后的匹配是不存在交叉线的。也就是说，如果第i高的男的和第j高的女的匹配，那么比i矮的男的就不能和比j高的女的匹配。同理，比i高的男的也就不能和比j矮的女的匹配。

2. 题目里有说男女的人数相差不到100，所以我们可以知道一个人的的可选匹配数量最多是100个。再加上这个性质，我们就可以用O(n * 100) = O(1000000)的DP来解决这个问题。相关的实现要用到滚存。

附上代码： (more…)

05 Apr 10 WHU2010校赛预赛G题：Pseudoforest

题目大意：给一个图，求这个图的最大伪森林生成树。所谓的伪森林就是图中的任意两个圈都没有公共部分。 (more…)

这个题目的意思给一个有向图，然后问有多少个key vertexes。一个点是key vertex的定义是，删掉这个点之后这个图的S-T就不连通了。

网络流的做法是比较显然的。在拆点然后跑网络流之后，所有的点割就都是key vertex。

题目里的点数比较多，有100000个之多，怎么求得高效的求得所有的点割是这个题目的另一个关键。

仔细观察残余网络的性质之后，可以得出一下算法：

这个做法的精巧实现使可以做到线性的。

这个题目是我出的，题意写的有点晦涩-.-!

不过简单表述起来还是挺简单的。

就是在一个圆上进行切割，每一次切割都要跨过整个圆。然后需要检查切割线，检查切割线的方法就是碰触切割出来的每一个小块。

说白了就是小块为点，相邻的小块连边，然后问进行点涂色，使得每一个边的两个端点至少有一个是涂色过了的。

解法：

通过一系列比较麻烦的几何处理之后，所求出来的图是一个二分图。然后求得二分匹配就是答案。

关于这个图是二分图的证明也有比较形象的理解，就是这个图是明显没有奇环的，所以就是二分图咯。。。