Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「POJ 2728」Desert King - 01 分数规划

一个王国有 N N 个城市,每个城市有坐标 (x,y) (x, y) 和海拔 z z ,在 N N 个城市之间修水渠,要保证每个城市有水,水渠是水平的,每个城市的海拔不同,现在要求修单位长度的水渠的海拔高度差最小。

链接

POJ 2728

题解

最优比率生成树,01 分数规划,搞的不是很明白 …… Orz

PS:果然我的代码自带大常数,搞了一早上不是 WA 就是 TLE,最后把编译器从 G++ 改为 VC++ 就 AC 了 ……

代码

#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAXN = 1000;
const int CACHE_FIX = 3;
const float EPS = 1e-4;

struct Node;
struct UndirectedEdge;

struct Node {
    int id;
    int x, y, z;
    bool inTree;
    UndirectedEdge *e;
} nodes[MAXN];

struct UndirectedEdge {
    float benifit, cost;
    float w;

    UndirectedEdge(float benifit, float cost) : benifit(benifit), cost(cost) {}
    UndirectedEdge() {}
} edges[MAXN + CACHE_FIX][MAXN];

int n;

inline float prim() {
    nodes[0].inTree = true;
    for (int i = 1; i < n; i++) nodes[i].e = &edges[0][i], nodes[i].inTree = false;

    float ans = 0;
    for (int i = 0; i < n - 1; i++) {
        Node *v = NULL;
        for (int i = 0; i < n; i++) if (!nodes[i].inTree && (v == NULL || nodes[i].e->w < v->e->w)) v = &nodes[i];

        ans += v->e->w;
        v->e = NULL;
        v->inTree = true;

        for (int i = 0; i < n; i++) if (!nodes[i].inTree && nodes[i].e->w > edges[i][v->id].w) nodes[i].e = &edges[i][v->id];
    }

    return ans;
}

inline float test(float p) {
    for (register int i = 0; i < n; i++) {
        for (register int j = i + 1; j < n; j++) {
            edges[j][i].w = edges[i][j].w = edges[i][j].cost - edges[i][j].benifit * p;
        }
    }

    float result = prim();
    //printf("test(%lf) = %lf\n", p, result);
    return result;
}

inline float solve(float sum) {
    register float l = 0, r = sum;
    //while (r - l > EPS) {
    for (int i = 0; i < 22; i++) {
        float mid = l + (r - l) / 2;
        if (test(mid) > 0) l = mid;
        else r = mid;
    }

    return l + (r - l) / 2;
}

inline float sqr(float x) {
    return x * x;
}

inline float distance(float x1, float x2, float y1, float y2) {
    return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}

int main() {
    while (scanf("%d", &n) != EOF && n != 0) {
        for (int i = 0; i < n; i++) nodes[i].id = i;

        for (int i = 0; i < n; i++) scanf("%d %d %d", &nodes[i].x, &nodes[i].y, &nodes[i].z);

        float sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                edges[j][i] = edges[i][j] = UndirectedEdge(distance(nodes[i].x, nodes[j].x, nodes[i].y, nodes[j].y), abs(nodes[i].z - nodes[j].z));
                sum += edges[i][j].benifit;
            }
        }

        float ans = solve(100);
        printf("%.3f\n", ans);
    }

    return 0;
}

数据生成器

#include <cstdio>
#include <cstdlib>
#include <ctime>

const int MAXN = 1000;

inline int luckyRand(int l, int r) {
    const int MAGIC_NUMBER = 20000528;
    const int x = rand();
    srand(x ^ ((time(NULL) << 16) | (clock() << 16 >> 16)) ^ MAGIC_NUMBER);
    return (rand() ^ x ^ MAGIC_NUMBER) % (r - l + 1) + l;
}

int main() {
    const int t = 3;
    const int n = MAXN;

    for (int i = 0; i < t; i++) {
        printf("%d\n", n);
        for (int i = 0; i < n; i++) {
            int x = luckyRand(luckyRand(0, 30), luckyRand(30, 60)), y = luckyRand(luckyRand(0, 30), luckyRand(30, 60)), z = luckyRand(luckyRand(0, 10000), luckyRand(90000, 100000));
            printf("%d %d %d\n", x, y, z);
        }
    }

    puts("0");

    return 0;
}
最近的文章

「UVa 11806」Cheerleaders - 组合数 + 容斥原理

在一个 MN M * N 的矩阵中摆放 K K 只石子,要求第一行、第一列、第 M M 行、第 N N 列必须有石子,求方案总数。

于  UVa, 容斥原理, 数学, 组合数学 继续阅读
更早的文章

「APIO2009」抢掠计划 - 强联通分量

城中的道路都是单向的。不同的道路由路口连接。在每个路口都设立了一个 ATM 取款机。酒吧也都设在路口,虽然并不是每个路口都设有酒吧。他将从市中心出发,沿着单向道路行驶,抢劫所有他途径的 ATM 机,最终他将在一个酒吧庆祝他的胜利。

他获知了每个 ATM 机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后,该 ATM 机里面就不会再有钱了。

于  APIO, BZOJ, Bellman-Ford, DAG, Tarjan, 强联通分量, 最长路, 缩点 继续阅读
comments powered by Disqus