BZOJ 1050 [HAOI2006]旅行comf

题目大意

给你一个无向图，求S->T的一条路径使得途径的所有边中$\frac{maxL}{minL}$最小。

数据范围 点数≤500,边数≤5000,边长≤30000

这道题我看到数据范围想了一会就基本想出来了，奋力码之，1A，开心。

首先看到这个第一想法肯定是枚举边长上界，因为不单调所以不可二分。之后重点就是使最小值最大。二分？二啥分啊上界都有了求下界多么轻松！并查集维护之，类似Kruskal往里加边直到S,T联通即可。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,s,t,fa[510],ansx,ansy=1;
int gcd(int tx,int ty)
{
	int tmp;
	while(ty)
	{
		tmp=tx;
		tx=ty;
		ty=tmp%ty;
	}
	return tx;
}
struct edge{int u,v,l;} e[5010];
bool cmp(edge tx,edge ty) {return tx.l<ty.l;}
void compare(int tx,int ty)
{
	if(ty==0) return;
	if(ansx==0)
	{
		ansx=tx,ansy=ty;
		return;
	}
	int tmp=gcd(ansy,ty);
	tx*=ansy/tmp;
	ansx*=ty/tmp;
	ansx=min(ansx,tx);
	ansy*=ty/tmp;
	tmp=gcd(ansx,ansy);
	ansx/=tmp,ansy/=tmp;
}
int unifind(int tx) {return fa[tx]==tx?tx:fa[tx]=unifind(fa[tx]);}
int check(int tx)
{
	for(int i=1;i<=n;++i) fa[i]=i;
	for(int i=tx;i;i--)
	{
		fa[e[i].u]=unifind(fa[e[i].u]),fa[e[i].v]=unifind(fa[e[i].v]);
		fa[fa[e[i].u]]=fa[e[i].v];
		if(unifind(t)==unifind(s)) return e[i].l;
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].l);
	scanf("%d%d",&s,&t);
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;++i) compare(e[i].l,check(i));
	if(!ansx) printf("IMPOSSIBLE");
	else
	{
		if(!(ansx%ansy)) printf("%d\n",ansx/ansy);
		else printf("%d/%d\n",ansx,ansy);
	}
	return 0; 
}