AcWing 348. 沙漠之王(0/1分数规划)

0/1分数规划

从该题可以归纳出的0/1分数规划的一般模型：给定正整数$a_1,a_2...a_n$以及$b_1,b_2...b_n$从中选出若干对的a和b的和的商，求商的最大值Max或者最小值Min，即：
$$\frac{{\sum }_{}a[i]}{{\sum }_{}b[i]}\in [Min,Max]$$

由于不知道他们的商是多少,我们不妨先假设$\frac{{\sum }_{}a[i]}{{\sum }_{}b[i]}=m$

find_Min

1.若 任意$\sum (a[i]-m\ast b[i])\ge 0$ ⇔ $\sum (a[i]-m\ast b[i]{)}_{min}\ge 0$ ⇔ $(\frac{\sum a[i]}{\sum b[i]}{)}_{min}\ge m$
即 $Min\ge m$
2.若 存在$\sum (a[i]-m\ast b[i])<0$ ⇔ $\sum (a[i]-m\ast b[i]{)}_{min}<0$ ⇔ $(\frac{\sum a[i]}{\sum b[i]}{)}_{min}<m$
即 $Min<m$

find_Max

1.若 存在$\sum (a[i]-m\ast b[i])\ge 0$ ⇔ $\sum (a[i]-m\ast b[i]{)}_{max}\ge 0$ ⇔ $(\frac{\sum a[i]}{\sum b[i]}{)}_{max}\ge m$
即 $Max\ge m$
2.若 任意$\sum (a[i]-m\ast b[i])<0$ ⇔ $\sum (a[i]-m\ast b[i]{)}_{max}<0$ ⇔ $(\frac{\sum a[i]}{\sum b[i]}{)}_{max}<m$
即 $Max<m$

二分

综上所诉,我们可以二分查找m
1.当$\frac{\sum a[i]}{\sum b[i]}\ge m$，即m ≤ {Max or Min}，→ l = mid;
2.当$\frac{\sum a[i]}{\sum b[i]}<m$，即m > {Max or Min}，→ r = mid;

348. 沙漠之王

思路：
成本为c， 长度为v
1.题意求生成树的$\frac{\sum c[i]}{\sum v[i]}$的Min, 不妨设$\frac{\sum c[i]}{\sum v[i]}=m$
2.若 任意$\sum (c[i]-m\ast v[i])\ge 0$
⇔ 以$(c[i]-m\ast v[i])$为边权的最小生成树
⇔ $\sum (c[i]-m\ast v[i]{)}_{min}\ge 0$
⇔ $(\frac{\sum c[i]}{\sum v[i]}{)}_{min}\ge m$
即 m 小于等于Min
则 l = mid 反正则 r = mid
3. 稠密图用prim算法$O(n^2)$, 用Kruskal$O(mlogm)$ ,$m=n^2$ 会超时
样例输入：

4
0 0 0
0 1 1
1 1 2
1 0 3
0

样例输出：

1.000

代码：

//最优比例生成树
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1005, M = 1e6 + 10, INF = 10000005;
typedef pair<int, int> PII;
int n;
double mm;double c[N][N], v[N][N], dist[N];
bool st[N];struct Point{int x, y, d;
}point[N];double dis(Point a, Point b)
{return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}double prim(double m)
{for(int i = 1; i <= n; i ++ ) dist[i] = INF;memset(st, false, sizeof st);double sum = 0;for(int i = 0; i < n; i ++ ){int t = -1;for(int j = 1; j <= n; j ++ )if(!st[j] && (t == -1 || dist[j] < dist[t]))t = j;if(i) sum += dist[t];for(int j = 1; j <= n; j ++ ){double tmp = c[t][j] - v[t][j] * m;if(!st[j]) dist[j] = min(dist[j], tmp);}st[t] = true;}return sum;
}int main()
{while(cin >> n){if(n == 0) break;for(int i = 1; i <= n; i ++ ){int x, y, d;cin >> x >> y >> d;point[i] = {x, y, d};}for(int i = 1; i <= n; i ++ )for(int j = i + 1; j <= n; j ++ ){c[i][j] = c[j][i] = (double)abs(point[i].d - point[j].d);v[i][j] = v[j][i] = dis(point[i], point[j]);}double l = 0, r = 100;while(r - l >= 1e-4){double mid = (l + r) / 2.0;if(prim(mid) >= 0) l = mid;else r = mid;}printf("%.3lf\n", r);        }return 0;
}