最大密集子图（01分数规划+二分+最小割）POJ3155

题意：给出一副连通图，求出一个子图令g=sigma(E)/sigma(V);

h[g]=sigma(E)-g*sigma(V)；设G是最优值

则当h[g]>0:g<G

h[g]<0,g>G;

h[g]=0：g=G；

h[g]=(U*n-Cut[S,T])/2;

当最小割Cut[S,T]最小时，h[g]最大

分析：建图方式：对于<u,v>,建立正向边和反向边容量为1

对于每个点u建立s->u容量为U，建立u->t容量为U+2*g-du(du是每个点的度)

公式推导详见：最小割模型在信息学竞赛中的应用

当h[g]>eps时增大g，否则减小g，知道h[g]=eps