题目链接：BZOJ(权限题) 、YALIOJ

Description

有n个城市(编号从0..n-1)，m条公路(双向的)，从中选择n-1条边，使得任意的两个城市能够连通，一条边需要的c的费用和t的时间，定义一个方案的权值v=n-1条边的费用和 * n-1条边的时间和，你的任务是求一个方案使得v最小

Solution

学习了一发最小乘积生成树，感觉好像特别巧妙 这题就是模板题

Code

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

using namespace std;

const int Maxn = 200 + 10, Maxm = 20000 + 10;

struct edge
{
    int x, y;
    int a, b, c;
}A[Maxm];

inline int cmp1 (edge u, edge v) {return u.a < v.a;}
inline int cmp2 (edge u, edge v) {return u.b < v.b;}
inline int cmp3 (edge u, edge v) {return u.c < v.c;}

struct point
{
    int x, y;
    bool operator < (const point &a) const
    {
        unsigned int p = x; p *= y;
        unsigned int q = a.x; q *= a.y;
        return q == p ? x < a.x : p < q;
    }
};

point Ans;

int N, M, fa[Maxn];

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

inline point MST ()
{
    for (int i = 1; i <= N; ++i) fa[i] = i;
    point now;
    now.x = now.y = 0;
    for (int i = 1; i <= M; ++i)
    {
        int fx = find(A[i].x), fy = find(A[i].y);
        if (fx != fy)
        {
            fa[fx] = fy;
            now.x += A[i].a;
            now.y += A[i].b;
        }
    }
//  cout<<now.x<<" "<<now.y<<endl;
    if (now < Ans) Ans = now;
    return now;
}

inline int mul (point a, point b, point c)
{
    return (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y);
}

inline void Solve (point a, point b)
{
    for (int i = 1; i <= M; ++i)
        A[i].c = A[i].b * (a.x - b.x) + A[i].a * (b.y - a.y);
    sort(A + 1, A + M + 1, cmp3);
    point c = MST();
    if (mul(a, b, c) <= 0) return ;
    Solve (a, c);
    Solve (c, b);
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    Ans.x = Ans.y = 1e9;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= M; ++i)
        scanf("%d%d%d%d", &A[i].x, &A[i].y, &A[i].a, &A[i].b), A[i].x ++, A[i].y ++;
    sort(A + 1, A + M + 1, cmp1);
    point a = MST();
    sort(A + 1, A + M + 1, cmp2);
    point b = MST();
    Solve (b, a);
    printf("%d %d\n", Ans.x, Ans.y);
    return 0;
}