分数规划/01规划

今天也是Mivik被智商碾压的一天啊QwQ

分数规划 貌似 和01规划是一个东西吧QwQ

问题

我们现在要求这样一个式子的最大值

$$
\frac{\sum e_i.a}{\sum e_i.b}
$$

其中 $e$ 中的元素是可以选择的，且 $e_i.a > 0$ ，$ e_i.b > 0$

我：这不是简单题吗？

---

垃圾Mivik的思路

首先对于每个矢量 $e_i$ ，求出它的性价比，即 $\frac{e_i.a}{e_i.b}$，然后在题目要求的范围内每次选出性价比最高的一个加入到集合 $e$ 中

但是这样会被卡QwQ

Hack：

要求在下面三个元素中选两个使得 $\frac{\sum e_i.a}{\sum e_i.b}$ 最大：

ID	a	b	性价比
1	2	1	2
2	3	1	3
3	2	0.1	20

显然2和3的性价比是最高的，我们按照贪心策略选出他们，最后的到的答案是

$$
\frac{1+3}{2+0.1}\approx1.90476
$$

但显然选1和2得出的答案更优

$$
\frac{2+3}{1+1}=2.5
$$

所以在有分数的情况下贪心是行不通的，因为：

$$
\sum \frac{e.a}{e.b}\not=\frac{\sum e.a}{\sum e.b}
$$

Mivik因此放弃了尝试~~

解题思路

我们设这个式子的最大值为ans，即

$$
Max(\frac{\sum e_i.a}{\sum e_i.b})=ans
$$

那么假设我们现在已经找到一种 $e$ 的组成方案，那么必有

$$
\frac{\sum e_i.a}{\sum e_i.b}\le ans \tag{1}
$$

移项，可得

$$
\sum e_i.a-\sum (ans \cdot e_i.b) \le 0 \tag{2}
$$

那么事情就变得很清晰了

我们只需要二分 $ans$ ，然后将 $e_i.a-(ans\cdot e_i.b)$ 作为 $e$ 的性价比，然后就可以用贪心做了

具体一点，如果我们当前枚举到的这个 $ans$ 使得用贪心（每次都选择性价比最小的 $e$ ）得出的 $e$ 集合满足 $(2)$ 式，也就是说满足 $(1)$ 式，那么说明我们的 $ans$ 是大于等于正确的 $ans$ ，那么我们就执行 $R=mid$ ，往下去二分正确的 $ans$ ，否则就 $L=mid$

为什么是 $L=mid$ 和 $R=mid$ 而不是 $L=mid+1$ 和 $R=mid-1$ 呢？

因为 $ans$ 是个小数，我们在对小数进行动态规划时不能加1啊QwQ

---

例题

P2868 - Sightseeing Cows 观光的奶牛

题意即给出一个有向图（没有重边），求出此无向图的一个环使得

$$
\frac{\sum V_i.f}{\sum E_i.d}
$$

最大，其中 $V$ ， $E$ 分别为环的点集和边集，且 $V_i.f$ 和 $E_i.d$ 都已经给出。

解题思路

我们按照上面的01规划对题中的式子变化一下

$$
\sum V_i.f-\sum (ans \cdot E_i.d) \le 0 \tag{3}
$$

但是！题目中要求我们求出来的必须是一个环，这就限定了 $V$ 和 $E$ 必须构成一个环，这该怎么办呢？

我们来观察一个环

我们不难发现

这个节点数为4的环可以被分成4个部分

其中，每一个部分都包含了一个点和从这个点出去的一条边

因此我们考虑在原图上跑最短路，每走一条边 $e$ 就把 $dis[e.to]$ 更新为

$$
min{dis[e.to],dis[e.from]+e.from.f-ans\cdot e.d}
$$

那么我们如果最后检测出了负环，那说明这个环上的 $V$ 和 $E$ 是满足式 $(3)$ 的，那么我们按照上面给出的思路二分就好了

代码实现

#include <iostream>
#include <cstdio>

#define endl '\n'
#define USING_R(fn,n) n fn() {static n _R;static char _C;static bool _F;_F=0;_R=0;_C=GG();while((_C<'0'||_C>'9')&&_C!='-'&&_C!='\0')_C=GG();if(_C=='-')_F=1,_C=GG();while(_C>='0'&&_C<='9')_R=(_R<<3)+(_R<<1)+_C-'0',_C=GG();if (_F) _R=-_R;return _R;}
#define R Read()
#define GG getchar

#define nmax 1005
#define mmax 5005
#define eps 1e-4
using namespace std;

USING_R(Read,int)
int n,m;
int re[nmax];
int lst[nmax];
int pre[mmax],tar[mmax],wei[mmax];
bool vi[nmax],fu[nmax];
double dis[nmax];
double T;
bool dfs(int x) {
	vi[x]=1;
	fu[x]=1;
	double w;
	for (int b=lst[x],v;b;b=pre[b]) {
		v=tar[b];
		w=dis[x]+wei[b]*T-re[v];
		if (w<dis[v]) {
			dis[v]=w;
			if (vi[v]) return 1;
			if (dfs(v)) return 1;
		}
	}
	vi[x]=0;
	return 0;
}
bool check() {
	for (int i=1;i<=n;i++) vi[i]=dis[i]=fu[i]=0;
	for (int i=1;i<=n;i++) if (!fu[i]) if (dfs(i)) return 1;
	return 0;
}
int main() {
	n=R,m=R;
	register int i,j;
	double l=0,r=0;
	for (i=1;i<=n;i++) r+=re[i]=R;
	for (i=1;i<=m;i++) {
		j=R;
		pre[i]=lst[j],lst[j]=i;
		tar[i]=R,wei[i]=R;
	}
	
	while (r-l>eps) {
		T=(l+r)/2;
		if (check()) l=T;
		else r=T;
	}
	printf("%.2f",l);
	return 0;
}

更多例题

P3288 [SCOI2014]方伯伯运椰子

---

（终于写完，Mivik快废了）

（纯手绘，图丑勿喷）