Day3T1

[丁丛煜 (M4 SOP MOD II)]

problemId:11001

Day3 T1

题意：

有一张无向图 $G(x)$，图中每条边的权值可以表达为 $ax+b$，对于在 l \sim r 之间的每一个 $x$，使得这张图的最小生成树最大的那一个 $x$，所对应的最小生成树的权值是多少。

思路：

40分：

对于 a_i=0 的数据，则边权是固定的，直接算一遍最小生成树即可。

然后对于 r-l\le 10 的点，我直接枚举整数（x可以是小数），然后得了 30 \text{pts} 然后一共 $40 \text{pts}$。

正解：

考虑三分，然后对于函数值 f(x') 就表示当 x=x' 时 最小生成树的值。

然后就是卡精度，实测最多可以卡到 \text{eps}=10^{-6} 三分次数 $44$。

\text{AC Code}

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-6;

int n, m;
struct Node {
    int u, v;
    int a, b;
    double w;
} e[100010];
int p[100010];

int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}

double f(double x) {
    double ans = 0;
    for (int i = 1; i <= n; ++i) p[i] = i;
    for (int i = 1; i <= m; ++i) e[i].w = 1.0 * e[i].a * x + 1.0 * e[i].b;
    sort(e + 1, e + 1 + m, [&](Node a, Node b) {
        return a.w < b.w;
    });
    for (int i = 1; i <= m; ++i) {
        int fa = find(e[i].u), fb = find(e[i].v);
        if (fa == fb) continue;
        p[fa] = fb;
        ans += e[i].w;
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v, a, b;
        scanf("%d%d%d%d", &u, &v, &a, &b);
        e[i] = {u, v, a, b};
    }
    double l, r;
    scanf("%lf%lf", &l, &r);
    for (int i = 1; i <= 44; ++i) {
        double mid = (l + r) / 2.0;
        double fl = f(mid - eps), fr = f(mid + eps);
        if (fl < fr)
            l = mid;
        else
            r = mid;
    }
    printf("%.3lf\n", max({f(l), f(r), f((l + r) / 2.0)}));
    return 0;
}