「BZOJ1050」[HAOI2006]旅行

Description

给你一个无向图,N(N500)N(N\leq 500)个顶点, M(M5000)M(M\leq 5000)条边,每条边有一个权值Vi(Vi<30000)V_i(V_i<30000)。给你两个顶点SSTT,求一条路径,使得路径上最大边和最小边的比值最小。如果SSTT之间没有路径,输出”IMPOSSIBLE”,否则输出这个比值,如果需要,表示成一个既约分数。
备注: 两个顶点之间可能有多条路径。

Input

第一行包含两个正整数,NNMM。下来的MM行每行包含三个正整数:xxyyvv。表示景点xx到景点yy之间有一条双向公路,车辆必须以速度vv在该公路上行驶。最后一行包含两个正整数sstt,表示想知道从景点ss到景点tt最大最小速度比最小的路径。sstt不可能相同。
1<N5001<N\leq 500,1x1\leq x,yNy\leq N0<v<300000<v<300000<M50000<M\leq 5000

Output

如果景点ss到景点tt没有路径,输出“IMPOSSIBLE”。否则输出一个数,表示最小的速度比。
如果需要,输出一个既约分数。

Sample Input

【样例输入1】

1
2
3
4
4 2
1 2 1
3 4 2
1 4

【样例输入2】

1
2
3
4
5
3 3
1 2 10
1 2 5
2 3 8
1 3

【样例输入3】

1
2
3
4
3 2
1 2 2
2 3 4
1 3

Sample Output

【样例输出1】

1
IMPOSSIBLE

【样例输出2】

1
5/4

【样例输出3】

1
2

Solution

force

先按照权值大小从小到大排序所有边。
枚举最大权值的边,然后对[1,i][1,i]的边倒着跑*kruskalkruskal,遍历的时候,如果sstt联通就马上退出。此时的边jj就是最小边,边ii就是最大边。时间复杂度是O(m2)O(m^2)

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch \leq '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 510, M = 5100;
struct Edge {
int u, v, w;
}e[M];
bool cmp(Edge _x, Edge _y) {
return _x.w < _y.w;
}
int n, m;
int fa[N];
int Find(int x) {
return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
int gcd(int x, int y) {
if(!y) return x;
return gcd(y, x %y);
}
int s, t;
int main() {
n = read(), m =read();
for(int i = 1; i \leq m; ++i) {
e[i].u = read(), e[i].v = read();
e[i].w = read();
}
s = read(), t = read();
sort(e + 1, e + 1 + m, cmp);
int ans1 = -1e9;
int ans2 = 1;
for(int i = 1; i \leq m; ++i) {
for(int j = 1; j \leq n; ++j) fa[j] = j;
int tmp1 = 1e9;
for(int j = i; j ; --j) {
int x = e[j].u, y = e[j].v;
x = Find(x);
y = Find(y);
if(x != y) {
fa[x] = y;
tmp1 = e[j].w;
}
if(Find(s) == Find(t)) break;
}
if(Find(s) == Find(t) && (double) tmp1 / e[i].w > (double) ans1 / ans2) {
ans1 = tmp1;
ans2 = e[i].w;
}
}
if(ans1 == -1e9) puts("IMPOSSIBLE");
else {
int t = gcd(ans1, ans2);
ans1 /= t;ans2 /= t;
if(ans1 == 1) printf("%d\n", ans2);
else
printf("%d/%d\n", ans2,ans1);
}
return 0;
}

std

最小生成树用lctlct维护,时间复杂度是O(mlogm)O(m log m)
按照边权从小到大枚举边,如果出现最优解,就替换。
他们联通的那一刻是最大边是ii,最小权值是jj
之后会出现一直findroot(x)=findroot(y)findroot(x) = findroot(y)
如果当前的边构成环,就删掉xyx\to y上权值最小一条边,此时他们不连通, 加上边ii他们就联通,此时sts\to t 一定经过边ii,那么查询两点之间最小权值就得到答案了。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 11000, M = 5100;
struct Edge {
int u, v, w;
}e[M];
bool cmp(Edge _x, Edge _y) {
return _x.w < _y.w;
}
int n, m;
struct lct {
int ch[N][2], tot;
int fa[N], val[N], c[N];
bool ident(int x) {
return ch[fa[x]][1] == x;
}
bool nr(int x) {
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
void up(int x) {
val[x] = min(val[ch[x][0]], val[ch[x][1]]);
val[x] = min(val[x], c[x]);
}
int r[N];
void down(int x) {
if(r[x]) {
r[x] = 0;
swap(ch[x][0], ch[x][1]);
r[ch[x][0]] ^= 1;
r[ch[x][1]] ^= 1;
}
}
void con(int x, int F, int how) {
ch[F][how] = x;
fa[x] = F;
}
void rotate(int x) {
if(ident(x)) {
int y = fa[x];
int z = ch[x][0];
fa[x] = fa[y];
if(nr(y))
con(x, fa[y], ident(y));
con(y, x, 0);
con(z, y, 1);
up(y); up(x);
} else {
int y = fa[x];
int z = ch[x][1];
fa[x] = fa[y];
if(nr(y))
con(x, fa[y], ident(y));
con(y, x, 1);
con(z, y, 0);
up(y); up(x);
}
}
int st[N], top;
void splay(int x) {
top = 0;
int y = x;
while(nr(y)) st[++top] = y, y = fa[y];
st[++top] = y;
while(top) down(st[top--]);
for(int y = fa[x]; nr(x); y = fa[x]) {
if(nr(y)) rotate(ident(y) == ident(x) ? y : x);
rotate(x);
}
}
void access(int x) {
for(int y = 0; x; x = fa[y = x])
splay(x), ch[x][1] = y, up(x);
}
void makeroot(int x) {
access(x);
splay(x);
r[x] ^= 1;
}
int findroot(int x) {
access(x);
splay(x);
while(ch[x][0]) x = ch[x][0];
return x;
}
void cut(int x, int y) {
makeroot(x);
if(findroot(y) != x || fa[x] != y || ch[y][0] != x) return;
ch[y][0] = fa[x] = 0;
}
void link(int x, int y) {
makeroot(x);
if(findroot(y) == x) return;
//fa[y] = x;
fa[x] = y;
}
int query(int x, int y) {
makeroot(y);
access(x);
splay(x);
return val[x];
}
}lct;
int gcd(int x, int y) {
if(!y) return x;
return gcd(y, x %y);
}
int main() {
freopen("1050.in","r",stdin);
freopen("1050.out","w",stdout);
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
e[i].u = x;
e[i].v = y;
e[i].w = read();
}
int s = read(), t = read();
memset(lct.c,0x3f,sizeof lct.c);
memset(lct.val,0x3f,sizeof lct.val);
sort(e + 1, e + 1 + m, cmp);
int ans1 = 1e9, ans2 = 1;
for(int i = 1; i <= m; ++i) {
int x = e[i].u, y = e[i].v;
if(x == y) continue;
if(lct.findroot(x) == lct.findroot(y)) {
int b = lct.query(x, y);
lct.cut(b + n, e[b].u);
lct.cut(b + n, e[b].v);
}
lct.c[i + n] = lct.val[i + n] = i;
lct.link(x, i + n);
lct.link(y, i + n);
if(lct.findroot(s) == lct.findroot(t)) {
int b = lct.query(s, t);
if(b <= m && (double)e[i].w / e[b].w < (double) ans1 / ans2) {
ans1 = e[i].w;
ans2 = e[b].w;
}
}
}
if(ans1 == 1e9) puts("IMPOSSIBLE");
else {
int t =gcd(ans1, ans2);
ans1 /= t, ans2 /= t;
if(ans2 == 1) writeln(ans1);
else printf("%d/%d\n", ans1, ans2);
}
return 0;
}