[BZOJ-1050]旅行

图论高级数据结构

Description

给你一张n个点m条边的无向图，有两个点s和t。
询问从s到t的路径中，最大边权与最小边权的比值最小是多少。

Solution

这是一道[HAOI2006]的题。
我们可以用LCT做这道题。
我们给边按边权从小到大排序，每次加入一条边。
如果要加入的这条边的两个顶点已经联通了，就找到联通的路径上的最小边把它删掉。
然后再连上这条边。然后统计一下答案即可。
因为我们按次序枚举边，所以当前s到t路径上的最大边一定是当前边，所以我们要最小边权尽量大，所以删掉最小的边。

我们给边按边权从小到大排序后，枚举最小的边。然后像Kruskal一样做，直到s到t联通。
因为这样最小边权是确定的，想要比值小，所以要最大边权尽量小，做最小生成树即可。

Notice

我们用LCT维护路径上的最小边权和最大边权时，情况有点复杂。

Code

LCT:

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define sqz main
#define ll long long
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define Rep(i, a, b) for (int i = (a); i < (b); i++)
#define travel(i, u) for (int i = head[u]; ~i; i = edge[i].next)

const ll INF = 1e9, Mo = INF + 7;
const int N = 5500;
const double eps = 1e-6;
namespace slow_IO
{
    ll read()
    {
        ll x = 0; int zf = 1; char ch = getchar();
        while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
        if (ch == '-') zf = -1, ch = getchar();
        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
        return x * zf;
    }
    void write(ll y)
    {
        if (y < 0) putchar('-'), y = -y;
        if (y > 9) write(y / 10);
        putchar(y % 10 + '0');
    }
}
using namespace slow_IO;

int cnt = 0, Maxans = INF, Minans = 1, n, m;
struct node
{
    int u, v, w;
}Edge[N + 5];
int cmp(node X, node Y)
{
    return X.w < Y.w;
}
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

struct LinkCutTree
{
    int Val[N + 5], Min[N + 5], Max[N + 5], Son[N + 5][2], rev[N + 5], Stack[N + 5], Fa[N + 5], top;
    inline int isroot(int x)
    {
        return Son[Fa[x]][0] != x && Son[Fa[x]][1] != x;
    }
    inline int VMin(int t)
    {
        return t != -1 ? t : INF;
    }
    inline int VMax(int t)
    {
        return t != -1 ? t : 0;
    }
    inline void up(int x)
    {
        Min[x] = Max[x] = x;
        if (VMin(Val[Min[Son[x][0]]]) < VMin(Val[Min[x]])) Min[x] = Min[Son[x][0]];
        if (VMin(Val[Min[Son[x][1]]]) < VMin(Val[Min[x]])) Min[x] = Min[Son[x][1]];
        if (VMax(Val[Max[Son[x][0]]]) > VMax(Val[Max[x]])) Max[x] = Max[Son[x][0]];
        if (VMax(Val[Max[Son[x][1]]]) > VMax(Val[Max[x]])) Max[x] = Max[Son[x][1]];
    }
    inline void down(int x)
    {
        if (rev[x])
        {
            rev[Son[x][0]] ^= 1, rev[Son[x][1]] ^= 1, rev[x] ^= 1;
            swap(Son[x][0], Son[x][1]);
        }
    }

    inline void Rotate(int x)
    {
        int y = Fa[x], z = Fa[y], l = Son[y][1] == x, r = l ^ 1;
        if (!isroot(y)) Son[z][Son[z][1] == y] = x;
        Son[y][l] = Son[x][r], Fa[Son[x][r]] = y;
        Son[x][r] = y, Fa[y] = x, Fa[x] = z;
        up(y), up(x);
    }
    inline void Splay(int x)
    {
        Stack[top = 1] = x;
        for (int i = x; !isroot(i); i = Fa[i]) Stack[++top] = Fa[i];
        per(i, top, 1) down(Stack[i]);
        while (!isroot(x))
        {
            int y = Fa[x], z = Fa[y];
            if (!isroot(y))
            {
                if ((Son[y][1] == x) ^ (Son[z][1] == y)) Rotate(x);
                else Rotate(y);
            }
            Rotate(x);
        }
    }

    inline void Access(int x)
    {
        for (int last = 0; x; last = x, x = Fa[x])
            Splay(x), Son[x][1] = last, up(x);
    }
    inline void Make_Root(int x)
    {
        Access(x), Splay(x), rev[x] ^= 1;
    }
    inline int Find_Root(int x)
    {
        Access(x), Splay(x);
        while (Son[x][0]) x = Son[x][0];
        return x;
    }

    inline void Split(int x, int y)
    {
        Make_Root(x), Access(y), Splay(y);
    }
    inline void Link(int x, int y)
    {
        Make_Root(x), Access(y), Splay(y);
        if (Find_Root(x) == Find_Root(y)) return;
        Fa[x] = y;
    }
    inline void Cut(int x, int y)
    {
        Make_Root(x), Access(y), Splay(y);
        if (Find_Root(x) != Find_Root(y) || Fa[x] != y || Son[x][1]) return;
        Fa[x] = Son[y][0] = 0;
    }
}LCT;

int sqz()
{
    n = read(), m = read();
    rep(i, 1, m)
    {
        int x = read(), y = read(), z = read();
        if (x != y) Edge[++cnt].u = x, Edge[cnt].v = y, Edge[cnt].w = z;
    }
    rep(i, 0, n + cnt) LCT.Val[i] = -1, LCT.Min[i] = LCT.Max[i] = i;
    int s = read(), t = read();
    s += cnt, t += cnt;
    sort(Edge + 1, Edge + cnt + 1, cmp);
    rep(i, 1, cnt)
    {
        int u = Edge[i].u + cnt, v = Edge[i].v + cnt; LCT.Val[i] = Edge[i].w;
        if (LCT.Find_Root(u) == LCT.Find_Root(v))
        {
            LCT.Split(u, v);
            int t = LCT.Min[v];
            LCT.Cut(Edge[t].u + cnt, t);
            LCT.Cut(Edge[t].v + cnt, t);
        }
        LCT.Link(u, i); LCT.Link(v, i);
        if (LCT.Find_Root(s) != LCT.Find_Root(t)) continue;
        LCT.Split(s, t);
        if ((double)LCT.Val[LCT.Max[t]] / LCT.Val[LCT.Min[t]] < (double)Maxans / Minans)
            Maxans = LCT.Val[LCT.Max[t]], Minans = LCT.Val[LCT.Min[t]];
    }
    int g = gcd(Maxans, Minans); Maxans /= g, Minans /= g;
    if (Maxans == INF) puts("IMPOSSIBLE");
    else if (Minans == 1) printf("%d\n", Maxans);
    else printf("%d/%d\n", Maxans, Minans);
    return 0;
}

最小生成树:

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
//
//  BZOJ-1050.cpp
//  图论/最小生成树
//
//  Created by 沈擎舟 on 2018/8/2.
//  Copyright © 2018年 Derec Emerald. All rights reserved.
//

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define sqz main
#define ll long long
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define Rep(i, a, b) for (int i = (a); i < (b); i++)
#define travel(i, u) for (int i = head[u]; ~i; i = edge[i].next)

const ll INF = 1e9, Mo = INF + 7;
const int N = 5500;
const double eps = 1e-6;
namespace slow_IO
{
    ll read()
    {
        ll x = 0; int zf = 1; char ch = getchar();
        while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
        if (ch == '-') zf = -1, ch = getchar();
        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
        return x * zf;
    }
    void write(ll y)
    {
        if (y < 0) putchar('-'), y = -y;
        if (y > 9) write(y / 10);
        putchar(y % 10 + '0');
    }
}
using namespace slow_IO;

int Fa[N + 5];
int Maxans = INF, Minans = 1;
struct node
{
    int u, v, w;
}Edge[N + 5];
int cmp(node X, node Y)
{
    return X.w < Y.w;
}
int Find(int x)
{
    return Fa[x] == x ? x : Fa[x] = Find(Fa[x]);
}
int gcd(int x, int y)
{
    return y ? gcd(y, x % y) : x;
}

int sqz()
{
    int n = read(), m = read();
    rep(i, 1, m) Edge[i].u = read(), Edge[i].v = read(), Edge[i].w = read();
    sort(Edge + 1, Edge + m + 1, cmp);
    int s = read(), t = read();
    rep(i, 1, m)
    {
        rep(j, 1, n) Fa[j] = j;
        rep(j, i, m)
        {
            int fx = Find(Edge[j].u), fy = Find(Edge[j].v);
            if (fx != fy) Fa[fx] = fy;
            if (Find(s) == Find(t))
            {
                if ((double)Edge[j].w / Edge[i].w < (double)Maxans / Minans)
                    Maxans = Edge[j].w, Minans = Edge[i].w;
                break;
            }
        }
    }
    int g = gcd(Maxans, Minans);
    Maxans /= g, Minans /= g;
    if (Maxans == INF) puts("IMPOSSIBLE");
    else if (Minans == 1) printf("%d\n", Maxans);
    else printf("%d/%d\n", Maxans, Minans);
    return 0;
}

文章目录
  1. 1. Description
  2. 2. Solution
  3. 3. Notice
  4. 4. Code