【题目大意】
给出一个有向图,问求一个回路,使得回路上的点权之和/边权之和 最大。
【解题思路】
转:此题是对01分数规划的应用,那么首先明白01分数规划的思想.
01整数规划问题就是求解方程(a1*x1+a2*x2+..+an*xn)/(b1*x1+b2*x2+..+bn*xn)的最小值/最大值问题。其中xi = 0或1(i=1,2...n)对于此类问题我们可以通过二分来求解很接近答案的近似值。我们可以先令:
(a1*x1+a2*x2+..+an*xn)/(b1*x1+b2*x2+..+bn*xn)=L,则我们可以将此式转换为:x1*(a1-b1*L)+x2*(a2-b2*L)+...xn*(an-bn*L)=0,我们先定义一个估......
阅读全文