[HAOI 2006]旅行comf
Description
给你一个 (n) 个点， (m) 条边的无向图。并给出一个点对 ((s,t)) ，求 (s,t) 间的一条路径，使得路径上最大边和最小边的比值最小。
(1leq nleq 500,1leq mleq 5000)
Solution
考虑用 (lct) 维护最小生成树。从大到小加边进 (lct) ，维护瓶颈路。剩下的就是 (lct) 维护边权的操作了。
好像这道题正解是暴力...
Code
//It is made by Awson on 2018.2.27
#include <bits/stdc++.h>
#define LL long long
#define dob complex<double>
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('
'))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = 1000, M = 5000;
void read(int &x) {
char ch; bool flag = 0;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
x *= 1-2*flag;
}
void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }
void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }
int n, m, u[N+5], w[N+5], v[N+5], fa[N+5], s, t; LL son = ~0u>>1, mom = 1;
struct tt {
int u, v, c;
bool operator < (const tt &b) const {return c > b.c; }
}e[M+5];
struct Link_Cut_Tree {
int ch[N+5][2], pre[N+5], isrt[N+5], rev[N+5], maxi[N+5], pos;
Link_Cut_Tree() {for (int i = 1; i <= N; i++) isrt[i] = 1; }
void pushup(int o) {
maxi[o] = o;
if (w[maxi[ch[o][0]]] > w[maxi[o]]) maxi[o] = maxi[ch[o][0]];
if (w[maxi[ch[o][1]]] > w[maxi[o]]) maxi[o] = maxi[ch[o][1]];
}
void pushdown(int o) {
if (rev[o] == 0) return;
int ls = ch[o][0], rs = ch[o][1]; Swap(ch[ls][0], ch[ls][1]), Swap(ch[rs][0], ch[rs][1]);
rev[ls] ^= 1, rev[rs] ^= 1, rev[o] = 0;
}
void push(int o) {if (isrt[o] == 0) push(pre[o]); pushdown(o); }
void rotate(int o, int kind) {
int p = pre[o];
ch[p][!kind] = ch[o][kind], pre[ch[o][kind]] = p;
if (isrt[p]) isrt[o] = 1, isrt[p] = 0; else ch[pre[p]][ch[pre[p]][1] == p] = o; pre[o] = pre[p];
ch[o][kind] = p, pre[p] = o; pushup(p), pushup(o);
}
void splay(int o) {
push(o);
while (isrt[o] == 0) {
if (isrt[pre[o]]) rotate(o, ch[pre[o]][0] == o);
else {
int p = pre[o], kind = ch[pre[p]][0] == p;
if (ch[p][kind] == o) rotate(o, !kind), rotate(o, kind);
else rotate(p, kind), rotate(o, kind);
}
}
}
void access(int o) {
int y = 0;
while (o) {
splay(o);
isrt[ch[o][1]] = 1, isrt[ch[o][1] = y] = 0;
pushup(o); o = pre[y = o];
}
}
void makeroot(int o) {access(o); splay(o); rev[o] ^= 1; Swap(ch[o][0], ch[o][1]); }
void split(int x, int y) {makeroot(x); access(y); splay(y); }
void link(int x, int y) {makeroot(x); pre[x] = y; }
void cut(int x, int y) {split(x, y); ch[y][0] = pre[x] = 0; isrt[x] = 1; pushup(y); }
void update(int x, int y, int c) {
split(x, y); int last = maxi[y]; w[last] = c;
cut(u[last], last), cut(v[last], last);
link(u[last] = x, last), link(v[last] = y, last);
}
int query(int x, int y) {split(x, y); return w[maxi[y]]; }
}T;
int find(int o) {return fa[o] ? fa[o] = find(fa[o]) : o; }
LL gcd(LL a, LL b) {return b ? gcd(b, a%b) : a; }
void work() {
read(n), read(m); T.pos = n;
for (int i = 1; i <= m; i++) read(e[i].u), read(e[i].v), read(e[i].c);
sort(e+1, e+m+1); read(s), read(t);
for (int i = 1; i <= m; i++) {
if (e[i].u == e[i].v) continue;
if (find(e[i].u)^find(e[i].v)) {
fa[find(e[i].u)] = find(e[i].v); w[++T.pos] = e[i].c;
T.link(u[T.pos] = e[i].u, T.pos), T.link(v[T.pos] = e[i].v, T.pos);
}else T.update(e[i].u, e[i].v, e[i].c);
if (find(s) == find(t)) {
LL p = T.query(s, t), q = e[i].c, d = gcd(p, q); p /= d, q /= d;
if (son*q > p*mom) son = p, mom = q;
}
}
if (son == ~0u>>1) puts("IMPOSSIBLE"); else if (mom == 1) writeln(son); else write(son), putchar('/') ,writeln(mom);
}
int main() {
work(); return 0;
}