最小乘积生成树。

感觉这个东西还是写一写记下来比较好.

总是懒得写博客不是个好习惯啊, 容易忘东西, 就造成学了没有用, 这是很不应该的事.

Description

给一条边两个权值 $A, B$, 使得$\sum{A} \times \sum{B}$最小.

Solution

我们定义一个$K = X \times Y$, 其中$X = \sum{A}, Y = \sum{B}$.

那么就有 $Y = \frac{K}{X}$, 这是一个反比例函数.

要最小化$K$就意味着要让函数上所有的点尽可能靠近坐标轴, 这是很形象的.

那么对于两个点确定的一个反比例函数, 我们希望找到一个相对于两点构成的直线更靠近坐标轴的点, 然后和某一个点确定一个新的反比例函数.

最优的情况, 也就是点最靠近坐标轴的情况是:

对于当前x最小的符合函数的解$P$, 和$y$最小的解$Q$, 我们希望找到一个点$R$, 使得:$\overrightarrow{PQ} \times \overrightarrow{PR}$最小.

也即最小化: $(Q.x - P.x) \times (R.y - P.y) - (R.x - P.x) \times (Q.y - P.y)$.

那么就可以最小化: $R.y \times (Q.x - P.x) - R.x \times (Q.y - P.y)$, 因为其他项都是常数了.

这样就可以做最小生成树来解决了.

如果当前反比例函数找不到更优的函数了(不存在一个点使得叉积为负), 要退出过程.

可以到BZOJ 2395提交.

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 205;
const int maxm = 10005;

struct Vector {
  int x, y;
  Vector(int x_ = 0.0, int y_ = 0.0) : x(x_), y(y_){}
  inline Vector operator + (Vector rhs) {
    return Vector(x + rhs.x, y + rhs.y);
  } 
  inline Vector operator - (Vector rhs) {
    return Vector(x - rhs.x, y - rhs.y);
  }
  inline int operator ^ (Vector rhs) {
    return x * rhs.y - y * rhs.x;
  }
  inline bool operator < (const Vector &rhs) const {
    return x * y == rhs.x * rhs.y ? x < rhs.x : x * y < rhs.x * rhs.y;
  }
};
struct edge {
  int frm, to, w, t, c;
  inline bool operator < (const edge &rhs) const {
    return w < rhs.w;
  }
}e[maxm];
int n, m, f[maxn];
Vector ans;

int find(int x) {
  return (f[x] == x) ? x : f[x] = find(f[x]);
}
inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
Vector kruskal() {
  Vector ret(0,0);
  for (int i = 1; i <= n; ++i) f[i] = i;
  sort(e + 1, e + 1 + m);
  for (int i = 1; i <= m; ++i) {
    int fx = find(e[i].frm), fy = find(e[i].to);
    if (fx != fy) {
      ret.x += e[i].c;
      ret.y += e[i].t;
      f[fx] = fy;
    }
  }
  ans = min(ans, ret);
  return ret;
}
void solve(Vector L, Vector R) {
  for (int i = 1; i <= m; ++i) {
    e[i].w = (R.x - L.x) * e[i].t - (R.y - L.y) * e[i].c;
  }
  Vector ret = kruskal();
  if (((R - L) ^ (ret - L)) >= 0) return;
  solve(L, ret); solve(ret, R);
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    e[i].frm = rd() + 1;
    e[i].to = rd() + 1;
    e[i].c = rd();
    e[i].t = rd();
  }
  ans = Vector(0x3f3f3f3f, 1);
  for (int i = 1; i <= m; ++i) e[i].w = e[i].t;
  Vector T = kruskal();
  for (int i = 1; i <= m; ++i) e[i].w = e[i].c;
  Vector C = kruskal();
  solve(C, T);
  printf("%d %d\n", ans.x, ans.y);
  return 0;
}