RenaMoe's Blog

念念不忘，必有回响

0%

题解 bzoj#2395 [Balkan 2011]Timeismoney

发表于 分类于 ， Valine：

题面

给出一个 n 点 m 边的无向图，每个边有权值 \(c_i,t_i\)，求出一个生成树使最小化： \[ (\sum_{i=1}^m c_i)\times(\sum_{i=1}^m t_i) \] \(1\le n\le 200,1\le m\le 1\times 10^4\)

思路

不同寻常的最小生成树。

转化题意

先对于所有生成树的答案，设 \(C=\sum c_i,T=\sum t_i\)，把他们表示成一个二维平面上若干个点（x 表示 C，y 表示 T）。

那么要最小化 \(C\times T\)，就是用一个曲线 \(y=\frac{C\times T}{x}\) 在这些点中取值，答案点一定在这些点的左下凸壳上。

接下来就是考虑怎么求出所有左下凸壳上的点来更新答案。

分治

先考虑凸壳上的极值：C 最小时，该点表示以 c 为边权做最小生成树的答案；T 最小时，该点表示以 t 为边权做最小生成树的答案。

设以上两个点为 P,Q，我们把 P,Q 相连，然后找到点 S 使得 \(S_{\triangle PQS}\) 最大，则 S 一定在凸壳上。

利用叉积来求三角形面积的话，已知 \(P=(x_1,y_1),Q=(x_2,y_2),S=(x,y)\)： \[ \begin{align} 2S_{\triangle PQS}&=\vec{PS}\times\vec{PQ}\\ &=(x-x_1,y-y_1)\times(x_2-x_1,y_2-y_1)\\ &=(x-x_1)(y_2-y_1)-(x_2-x_1)(y-y_1)\\ &=(y_2-y_1)x-(x_2-x_1)y-(y_2-y_1)x_1+(x_2-x_1)y_1 \end{align} \] 忽略后面两项常数，可以转化成最小化 \((x_2-x_1)y-(y_2-y_1)x\)。

那么把所有边权重新赋为 \((x_2-x_1)t-(y_2-y_1)c\)，跑一边最小生成树即可找到点 S。

以 S 划分，分治下去即可。

注意边界：如果找到的点 S 在 PQ 直线上方（通过叉积判断），那么凸壳上 P,Q 相邻，不再分治。

复杂度

不是很懂，O(能过)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

namespace RenaMoe {
template <typename TT> inline void read(TT &x) {}

typedef long long LL;
const int N = 1e4 + 9;

struct Edge {
    int x, y;
    LL c, t, val;
    bool operator <(const Edge &t) const {
        return val < t.val;
    }
};
struct Point {
    LL x, y;
    Point() {}
    Point(LL _x, LL _y) : x(_x), y(_y) {}
    bool operator <(const Point &t) const {
        return x * y == t.x * t.y ? x < t.x : x * y < t.x * t.y;
    }
    Point operator -(const Point &t) const {
        return Point(x - t.x, y - t.y);
    }
    LL operator *(const Point &t) const {
        return x * t.y - y * t.x;
    }
};

int n, m;
Point ans;
int fa[N];
Edge e[N];

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

inline Point Kruskal() {
    Point re(0, 0);
    sort(e+1, e+m+1);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int x = find(e[i].x), y = find(e[i].y);
        if (x != y) {
            fa[x] = y;
            re.x += e[i].c, re.y += e[i].t;
        }
    }
    return re;
}

// l: P,  r: Q,  mid: S 
void solve(Point l, Point r) {
    for (int i = 1; i <= m; ++i)
        e[i].val = e[i].t * (r.x - l.x) - e[i].c * (r.y - l.y);
    Point mid = Kruskal();
    if ((mid - l) * (r - l) <= 0) return;
    ans = min(ans, mid);
    solve(l, mid), solve(mid, r);
}

inline void main() {
    read(n), read(m);
    for (int i = 1, u, v; i <= m; ++i) {
        read(u), read(v), read(e[i].c), read(e[i].t);
        e[i].x = u + 1, e[i].y = v + 1;
    }
    for (int i = 1; i <= m; ++i) e[i].val = e[i].c;
    Point l = Kruskal();
    for (int i = 1; i <= m; ++i) e[i].val = e[i].t;
    Point r = Kruskal();
    ans = min(l, r);
    solve(l, r);
    printf("%lld %lld\n", ans.x, ans.y);
}
}

int main() {
    RenaMoe::main();
    return 0;
}