学习动因

昨天多校(第四场)的04题 hdu 6070 Dirt Ratio 于是百度了一发发现叫做 01分数规划 的东西（还是姿势太少） 故先学习一发基础知识写几道入门题再去补 04 （后补了04，http://blog.csdn.net/kkkkahlua/article/details/76718763，觉得 04 最关键的还是那个线段树的理解…当然二分的想法来自分数规划，这一点还是很重要的）

参考资料

http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html ——PerSeAwe

入门题（3道）

原Po的文章里 知识点 和 题解 都写得很详细，我也没啥新的想法，在此就不赘述了，直接贴代码 （以及…看到Pascal真是亲切啊）

poj 2976

Code:

#include <cstdio> #include <cstring> #include <algorithm> #define maxn 1010 const double eps = 1e-7; using namespace std; int a[maxn], b[maxn], n, k; double d[maxn]; bool check(double x) { // printf("%f\n", x); for (int i = 0; i < n; ++i) d[i] = (double)a[i] - x * b[i]; sort(d, d + n); double sum = 0; for (int i = k; i < n; ++i) sum += d[i]; if (sum >= 0) return true; return false; } void work() { for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < n; ++i) scanf("%d", &b[i]); double l = 0, r = 1.0, mid; while (r - l > eps) { mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } printf("%.0f\n", mid * 100); } int main() { freopen("in.txt", "r", stdin); while (scanf("%d%d", &n, &k) != EOF && n + k) work(); return 0; }

poj 2728

Code:

#include <cstdio> #include <cstring> #include <cmath> #define eps 1e-5 #define inf 0x3f3f3f3f #define maxn 1010 using namespace std; int cost[maxn][maxn], x[maxn], y[maxn], h[maxn], n; double len[maxn][maxn], dist[maxn], val[maxn][maxn]; bool vis[maxn]; inline int abs(int a) { return a > 0 ? a : -a; } bool check(double x) { // printf("%.3f\n", x); memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; ++i) dist[i] = inf; int src = 0; vis[src] = true; double sum = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) val[i][j] = cost[i][j] - x * len[i][j]; } for (int num = 0; num < n - 1; ++num) { double minn = inf; int p = -1; for (int i = 0; i < n; ++i) { if (vis[i]) continue; double vall = val[src][i]; dist[i] = vall < dist[i] ? vall : dist[i]; if (dist[i] < minn) { minn = dist[i]; p = i; } } sum += minn; vis[src = p] = true; // printf("%d ", src); } // printf("\n\n"); if (sum <= 0) return true; return false; } inline double max(double a, double b) { return a > b ? a : b; } void work() { for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &h[i]); double r = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { cost[i][j] = cost[j][i] = abs(h[i] - h[j]); len[i][j] = len[j][i] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])); r = max(r, cost[i][j] / len[i][j]); } } double l = 0.0, mid; // printf("%f\n", r); while (r - l > eps) { mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } printf("%.3f\n", mid); } int main() { freopen("in.txt", "r", stdin); freopen("2728.out", "w", stdout); while (scanf("%d", &n) != EOF && n) work(); return 0; }

poj 3621

Code:

#include <cstdio> #include <cstring> #define eps 1e-4 #define maxm 5010 #define maxn 1010 #define inf 0x3f3f3f3f using namespace std; int n, p, tot; double dist[maxn]; int a[maxn]; struct Edge { int from, to, cost, val; double d; Edge(int a = 0, int b = 0, int c = 0, int v = 0, double _d = 0.0) : from(a), to(b), cost(c), val(v), d(_d) {} }edge[maxm]; void add(int from, int to, int cost, int val) { edge[tot++] = Edge(from, to, cost, val); } inline double max(double a, double b) { return a > b ? a : b; } bool check(double x) { for (int i = 0; i < tot; ++i) edge[i].d = -(edge[i].val - x * edge[i].cost); // for (int i = 0; i < tot; ++i) printf("%d %d %d %d %.3f\n", edge[i].from, edge[i].to, edge[i].cost, edge[i].val, edge[i].d); int src = 1; for (int i = 1; i <= n; ++i) dist[i] = inf; dist[src] = 0; for (int i = 0; i < n; ++i) { bool flag = false; for (int j = 0; j < tot; ++j) { Edge e = edge[j]; if (dist[e.to] > dist[e.from] + e.d) { dist[e.to] = dist[e.from] + e.d; flag = true; } } // for (int j = 1; j <= n; ++j) printf("%.3f ", dist[j]); printf("\n"); if (!flag) return false; } return true; } void work() { tot = 0; for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); double r = 0; for (int i = 0; i < p; ++i) { int x, y, t; scanf("%d%d%d", &x, &y, &t); add(x, y, t, a[x]); r = max(r, (double)a[x] / t); } double l = 0.0, mid; while (r - l > eps) { mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } printf("%.2f\n", mid); } int main() { freopen("in.txt", "r", stdin); while (scanf("%d%d", &n, &p) != EOF) work(); return 0; }