Description
给定无向图中的两个点 (s,t),求一条 (s o t) 的路径,其最大边权和最小边权的比值最小。
Solution
(O(m log^2 n)) 解法
降序枚举最小边权,将满足条件的边全部加入 LCT,动态维护最小生成树即可
最小生成树上需要支持最大边查询
回忆一下怎么用 LCT 维护最小生成树,我们需要对边也建点,不妨记做 (i'),所有边权都记在 (i') 上,当需要加边 (i') 时连接 (i') 和它的两个端点 (u,v),断边时同理,询问是返回 (i'),这样就可以查表得到它的端点编号
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000000;
const int dbg = 0;
int n,m,val[N];
struct stredge
{
int u,v,w;
bool operator < (const stredge &obj) const
{
return w>obj.w;
}
} edge[N];
namespace lct
{
int top, q[N], ch[N][2], fa[N], rev[N];
int a[N], tag[N], siz[N];
inline void pushup(int x)
{
a[0] = siz[0] = 0;
a[x] = x;
if(val[a[ch[x][0]]]>val[a[x]]) a[x]=a[ch[x][0]];
if(val[a[ch[x][1]]]>val[a[x]]) a[x]=a[ch[x][1]];
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}
inline void pushdown(int x)
{
if(rev[x])
{
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
rev[x]^=1;
swap(ch[x][0],ch[x][1]);
}
}
inline bool isroot(int x)
{
return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
}
inline void rotate(int p)
{
int q=fa[p], y=fa[q], x=ch[fa[p]][1]==p;
ch[q][x]=ch[p][x^1];
fa[ch[q][x]]=q;
ch[p][x^1]=q;
fa[q]=p;
fa[p]=y;
if(y) if(ch[y][0]==q) ch[y][0]=p;
else if(ch[y][1]==q) ch[y][1]=p;
pushup(q);
pushup(p);
}
inline void splay(int x)
{
q[top=1]=x;
for(int i=x; !isroot(i); i=fa[i]) q[++top]=fa[i];
for(int i=top; i; i--) pushdown(q[i]);
for(; !isroot(x); rotate(x))
if(!isroot(fa[x]))
rotate((ch[fa[x]][0]==x)==(ch[fa[fa[x]]][0]==fa[x])?fa[x]:x);
}
void access(int x)
{
for(int t=0; x; t=x,x=fa[x])
splay(x),ch[x][1]=t,pushup(x);
}
void makeroot(int x)
{
access(x);
splay(x);
rev[x]^=1;
}
int find(int x)
{
access(x);
splay(x);
while(ch[x][0]) x=ch[x][0];
return x;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
void cut(int x,int y)
{
split(x,y);
if(ch[y][0]==x)
ch[y][0]=0, fa[x]=0;
}
void link(int x,int y)
{
if(find(x)==find(y)) return;
makeroot(x);
fa[x]=y;
pushup(y);
}
int query(int x,int y)
{
split(x,y);
return a[y];
}
}
void linkedge(int id)
{
lct::link(n+id,edge[id].u);
lct::link(n+id,edge[id].v);
}
void cutedge(int id)
{
lct::cut(n+id,edge[id].u);
lct::cut(n+id,edge[id].v);
}
int getmaxedge(int p,int q)
{
return lct::query(p,q)-n;
}
int getmaxweight(int p,int q)
{
return edge[getmaxedge(p,q)].w;
}
void tryedge(int id)
{
int u=edge[id].u,v=edge[id].v,w=edge[id].w;
if(lct::find(u)!=lct::find(v))
{
linkedge(id);
}
else
{
int mw=getmaxweight(u,v);
if(mw>w)
{
int mv=getmaxedge(u,v);
cutedge(mv);
linkedge(id);
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
edge[i]={u,v,w};
}
sort(edge+1,edge+m+1);
for(int i=1;i<=m;i++)
{
val[n+i]=edge[i].w;
}
int s,t;
cin>>s>>t;
int ansp=1,ansq=0;
for(int i=1;i<=m;i++)
{
if(dbg) cout<<"main() i="<<i<<endl;
tryedge(i);
if(lct::find(s)==lct::find(t))
{
//ans=min(ans,1.0*getmaxweight(s,t)/edge[i].w);
if(getmaxweight(s,t)*ansq<edge[i].w*ansp)
{
ansp=getmaxweight(s,t);
ansq=edge[i].w;
int g=__gcd(ansp,ansq);
if(g)
{
ansp/=g;
ansq/=g;
}
}
}
}
if(ansq==0)
{
cout<<"IMPOSSIBLE";
}
else if(ansq==1)
{
cout<<ansp;
}
else
{
cout<<ansp<<"/"<<ansq;
}
}