高分急求北大ACM 2943与3155两题的代码！！！

Hard Life
[Description]
给出无向图G(V, E), 求一个子图G'(V', E'), 使得比值|E'|/|V'|最大. (|V| <= 100, |E| <= 1000)
[Solution]
本题可以描述为:

其中Xv, Ye的取值为0或1, 表示点或边是否选取. 这是一个0-1分数规划(0-1 fractional programming). 可以通过如下参数搜索的方法解决. 关于答案 , 构造一个新问题 :

设原问题的最优解是 , 显然有 . 设两个变量 < . 由于 >= 0, 把 的最优解向量 , 代入 中, 必会得到一个更大的z值, 所以z单调递减. 所以有:

这就意味着可以进行二分搜索答案 . 注意初始范围: . 关于01分数规划参见[1]或最优比率生成树的解法.
这样将问题转化为求 的最大值. 它需要满足限制: 边(u, v)的选取, 需要点u, v的选取. 这样的依赖关系与函数的形式使我们想到了最小割来解决这类问题, 参见[2]. 建立二分图, X部的点Xv代表点v, Y部的点Ye代表边e. 若边e关联了2个点u, v, 则分别从Xu, Xv向Ye连一条容量为正无限的边. 再建立源S, 汇T. 由S向每个Xv连容量为λ的边, 由每个Ye向T连容量为 1的边. 这样求出该网络的最小割Mincut. 则 .

求最小割的过程使用最大流的Edmonds Karp算法. 点数为O(|V|+|E|), 边数为O(|E|). 每次找增广轨需O(|E|). 共增广O(|E|^2)次. 算法总复杂度为O(|E|^3 log R). 而实际情况会比这个估计好很多. 稀疏二分图的增广次数达不到O(|E|^2). 这题使用Relabel to front的Preflow Push算法O(|E|^3), 反而会超时.
另一解:

直接保留原图, 即若原图存在边(u, v), 从Xu到Xv连一条容量为正无限的边, 同时从Xv到Xu也连一条容量为正无限的边. 再建立源S, 汇T. 由S向每个Xv连容量为m的边, 由每个Xv向T连容量为m-Dv+2λ的边. 其中Dv表示点v的度. 若此网络的最小割, 即为z. 由于点数为O(|V|), 边数为O(|E|). 使用Preflow Push的复杂度为O(|V|^3), 效果很好.
[Reference]
[1] T. Matsui, Y. Saruwatari, Maiko Shigeno，An Analysis of Dinkelbach's Algorithm for 0-1 Fractional Programming Problems (1992)
[2] The Introduction to Algorithm, Problems 26-3: Space shuttle experiments.

看了一遍，感觉不好做

The Cow Doctor 看起来还不算太难
Hard Life 等我做完上一题再说

不会

哇。