最终得对抗自己

Categories » 分数规划

[POJ 3155] Hard Life 最大密度子图

给定无向图,点有点权,边有边权,一条边被选中当且仅当这条边链接的两个点被选中,现在求一个联通子图让所有被选中点权值之和除以被选中边的权值之和最小。

这就是最大密度子图问题了。

[POJ 3621] Sightseeing Cows 最大密度环

有向图中点有点权, 边有边权, 每个点的点权只能只能取一次, 可以任意选择起点, 求一个点权和除以边权和(密度)最大的回路。

01分数规划入门。