【算法竞赛进阶指南】 0/1分数规划 0

含义
给定两个集合a[N]，b[N]，每种集合中的物品都有两种形式0和1分别代表取和不取的状态，用x[N]和y[N]来表示，就是求 ∑ i = 1 N a [ i ] ? x [ i ] b [ i ] ? y [ i ] \sum\limits_{i=1}^{N}\frac{a[i]*x[i]}{b[i]*y[i]} i=1∑N?b[i]?y[i]a[i]?x[i]?的最值问题。
解法
遇到这种单调最值的问题，最简单的方法就是用二分的思想，我们可以先拟定一个答案mid= ∑ a [ i ] ∑ b [ i ] \frac{\sum{a[i]}}{\sum{b[i]}} ∑b[i]∑a[i]?，展开来就变成 ∑ a [ i ] \sum{a[i]} ∑a[i] - mid* ∑ b [ i ] \sum{b[i]} ∑b[i] = 0。然后我们可以调整mid的值去逼近最终的答案。
例子
1.比率最优环

文章图片

转换一下题意，就是求点权和边权和 \frac{点权和}{边权和} 边权和点权和?最大值，展开变成w(点权) - l（边权）* x（答案）= 0。然后就可以用上述方法把答案用二分来逼近，注意一下判断的技巧，如果结果为负数，那么可以直接用判负环的方法直接退出。

#include using namespace std; double eps = 1e-4; const int N = 1e3 + 5; const int M = 5e3 + 5; struct edge { int to, next; double vi; }e[M * 2]; int vis[N], n, cnt, m, h[N], times[N]; double dis[N]; int ve[N]; void add(int u, int v, double w) { e[cnt].to = v; e[cnt].vi = w; e[cnt].next = h[u]; h[u] = cnt++; } bool spfa(double mid) { queue q; for (int i = 1; i <= n; i++) { q.push(i); vis[i] = 1, dis[i] = 0, times[i] = 0; } while (q.size()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = h[u]; ~i; i = e[i].next) { int v = e[i].to; double va = mid * e[i].vi - (double)ve[u]; if (dis[v] > dis[u] + va) { dis[v] = dis[u] + va; times[v] = times[u] + 1; if (times[v] >= n) return true; if (!vis[v]) { q.push(v); vis[v] = 1; } } } } return false; } int main() { scanf("%d %d", &n, &m); memset(h, -1, sizeof h); for (int i = 1; i <= n; i++) scanf("%d", &ve[i]); for (int i = 1; i <= m; i++) { int x, y; double z; scanf("%d %d %lf", &x, &y, &z); add(x, y, z); }double l = 0, r = 1e4 + 1, mid; while (r - l > eps) { mid = (l + r) * 0.5; if (spfa(mid)) l = mid; else r = mid; } printf("%.2lf", mid); }

2.比率最优生成树

文章图片

成本=高度差
长度=欧式距离
转化一下就是 c o s t d i s \frac{cost}{dis} discost?的最小值
展开来变成cost - mid * dis = 0，要取mid的最小值，则不能存在更小的mid使cost - mid * dis<0，也就等价于最小生成树总边权>0恒成立
如果最小生成树都满足>0，那么所有树都满足，因此可以加大mid的值
【【算法竞赛进阶指南】 0/1分数规划】记得用prim，kruskal在边多的时候会超时=。=

#include using namespace std; const int N = 1e3 + 10; const int M = 1e6 + 10; const double INF = 0x3f3f3f3f; int n, pre[N]; double dis[N], vis[N], val[N], g[N][N], cost[N][N]; struct node { double x, y; }p[N]; double get_dis(node x, node y) { return sqrt((x.x - y.x)*(x.x - y.x) + (x.y - y.y)*(x.y - y.y)); } bool prim(double mid){for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = 0; dis[1] = 0; double ans = 0; for(int i = 1; i <= n; i++){ double mx = INF; int k = 1; for(int j = 1; j <= n; j++) if(!vis[j] && mx > dis[j]) mx = dis[j], k = j; vis[k] = 1; ans += dis[k]; for(int j = 1; j <= n; j++){ if(!vis[j] && dis[j] > cost[k][j] - mid * g[k][j]) dis[j] = cost[k][j] - mid * g[k][j]; } } return ans >= 0; }int main() { while (scanf("%d", &n) && n){ for (int i = 1; i <= n; i++) scanf("%lf %lf %lf", &p[i].x, &p[i].y, &val[i]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) continue; g[i][j] = get_dis(p[i], p[j]); cost[i][j] = fabs(val[j] - val[i]); } } double l = 0, r = 1e9+1, mid; while (r - l > 1e-6) { mid = (l+r)*0.5; if (prim(mid)) l = mid; else r = mid; } printf("%.3lf\n", mid); }}