l******y
发帖数: 472 | 1 对于一个无向图G, 对V的子集S，定义n(S)为图中端点都在S中的边的数目，
即n(S) = | {(u, v) | (u, v) ∈ E and u ∈ S, v ∈ S }| , 求使n(S)/|S|最大的S
题目提示说用网络流里面的min－cut思路来作，类似于project selection
project selection可以看这里http://en.wikipedia.org/wiki/Max-flow_min-
cut_theorem#Project_selection_problem | s*****n
发帖数: 5488 | |
|
