最优比例生成树

POJ 2728 Desert King

Posted on

01分数规划之最优比例生成树……
这道题,好坑……

一开始WA了,然后找了一个博客,WA,照着敲,WA,再照着敲,WA,索性复制再改,WA,最后复制粘贴,他的也WA了。md

感觉我写题的时候很容易石乐志,然后就很难过题……
好几场比赛都验证了……

题意:
给你一张图上的所有点,由所有点得出每条边的两个权值,欧式距离与高度差。
要你和找出一个生成树,使得 高度差的和比上欧式距离和最小。

思路:
最优比例生成树的经典题。其实只要掌握了01分数规划的思想,你就照着prime敲就好了。
我这里用了迭代法,感觉迭代法更套路一些……而且速度比较快。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const double inf = 0x3f3f3f3f3f;
const double eps = 1e-6;
const int maxn = 1e3 + 10;

int n;
double dist[maxn][maxn];
int x[maxn], y[maxn], h[maxn];
bool vis[maxn];
int pre[maxn];
double dis[maxn];

double prime(double L)
{
    double sc = 0, ss = 0;
    range(i, 1, n)
    {
        pre[i] = 1;
        dis[i] = abs(h[1] - h[i]) - dist[1][i] * L;
    }
    pre[1] = -1;
    range(i, 2, n)
    {
        double mi = inf;
        int v = -1;
        range(j, 1, n) if (pre[j] != -1 && dis[j] < mi)
        {
            v = j;
            mi = dis[j];
        }
        if (v != -1) {
            sc += abs(h[pre[v]] - h[v]);
            ss += dist[pre[v]][v];
            pre[v] = -1;
            range(j, 1, n)
            {
                double tmp = abs(h[v] - h[j]) - dist[v][j] * L;
                if (pre[j] != -1 && tmp < dis[j]) {
                    dis[j] = tmp;
                    pre[j] = v;
                }
            }
        }
    }
    return sc / ss;
}

inline double calc(int a, int b) { return (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]); }

int main()
{
    while (scanf("%d", &n) != EOF && n) {
        range(i, 1, n) scanf("%d %d %d", x + i, y + i, h + i);
        range(i, 1, n) range(j, i, n) dist[j][i] = dist[i][j] = sqrt(calc(i, j));
        double ans = 0, L;
        do {
            L = ans;
            ans = prime(L);
        } while (fabs(ans - L) >= eps);
        printf("%.3f\n", ans);
    }
    return 0;
}
最优比例环

POJ 3621 Sightseeing Cows

Posted on

分数划分之最优比例环。
分数划分中比较常见的限制之一,在图中筛选的必须是一个环。

本来在入门题的时候对于以下转换公式有考虑过这样的一个问题:

$ \sum \left( \left( a_{i}-L\times b_{i}\right) \times x_{i}\right) $

为什么只需要考虑 \( \left( a_{i}-L\times b_{i}\right) \) 与 \( 0 \) 之间的关系,而不用去管\( x_i \)了呢?明明取舍\( x_i \)也是对答案会造成影响的。

而实际上,举个例子,对于最优比例环来说,成不成环就是一个主要的筛选的过程。然后再是对于二分的值\( L \),如果对于当前\( L\) 仍有可提升空间。若仍有提升空间,就说明\( L\)可以更大。

不知不觉就跟学习资料上说的一模一样了
也许我自己也没有深刻理解,但还是有写意会了吧。

题意:
给你一张图,图上的每个节点和边都有权值。要你找出一个环,使得点权和 - 边权和最大。

思路:
我们要最大化 点权和 - 边权和,那么我们二分的时候就要找一个 \( L \) ,使得转化函数大于0。
因为对于一个环来说,他的点数与边数是相同的,所以我们在边权上处理一下就转化成了一个找正环的判定。
考虑到 spfa 只能用来求负环,那么就把边权取反即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const double eps = 1e-5;
const int maxn = 1e3 + 5;
const int maxm = 5e3 + 5;

int n, m, idx;
int val[maxn];
int head[maxn];

struct node {
    int to, weight;
    int next;
} edges[maxm << 1];

void addEdge(int u, int v, int w)
{
    edges[idx] = (node){ v, w, head[u] };
    head[u] = idx++;
}

queue<int> que;

bool spfa(int st, double key)
{
    while (!que.empty())
        que.pop();
    bool inq[maxn];
    double dis[maxn];
    int cnt[maxn];
    fill(cnt, 0), fill(inq, false);
    each(i,n+1) dis[i] = 0x3f3f3f3f;
    dis[st] = 0, inq[st] = true, cnt[st] = 1;
    que.push(st);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        inq[u] = false;
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            double w = 1.0 * edges[id].weight * key - val[v];
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!inq[v]) {
                    inq[v] = true;
                    que.push(v);
                    if (++cnt[v] >= n)
                        return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    int u, v, w;
    while (scanf("%d %d", &n, &m) != EOF) {
        fill(head, -1), idx = 0;
        range(i, 1, n) scanf("%d", val + i);
        each(i, m)
        {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
        }
        double l = 0, r = 2000, mid;
        while (l + eps < r) {
            mid = (l + r) / 2;
            if (spfa(1, mid))
                l = mid;
            else
                r = mid - eps;
        }
        printf("%.2f\n", l);
    }
    return 0;
}