题目链接

https://www.luogu.org/problemnew/show/P2502

分析

一个很\(naive\)的做法是从\(s\)到\(t\)双向BFS这当然会TLE

这时我就有个想法就是二分套二分边下标来求得一个比值,同时排序后从小到大枚举每一条边作为最小值,同时再枚举每一条边,如果边权之比小于比值就连起来用并查集维护连通性,可是这个时间复杂度\(O(m^2 log^2m \ \alpha(n))\)过不去QAQ

然后想为什么不直接枚举每条边作为最小值,同时搞一颗以这条边为最小值且联通s,t的最小生成树呢,因为边是排序好的,这样答案是单调的,且正确性是显然的时间复杂度\(O(m^2)\).

代码

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cctype>

#include <cmath>

#define ll long long

#define ri register int

using std::sort;

using std::min;

using std::max;

using std::swap;

template <class T>inline void read(T &x){

	x=0;int ne=0;char c;

	while(!isdigit(c=getchar()))ne=c=='-';

	x=c-48;

	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;

	x=ne?-x:x;return ;

}

const int maxm=5005;

const int maxn=505;

const int inf=0x7fffffff;

struct Edge{

	int x,y,dis;

	bool operator <(const Edge &b)const{

		return dis<b.dis;

	}

}edge[maxm];

int num_edge=0;

int n,m,s,t;

int fa[maxn];

int get(int x){return fa[x]==x?fa[x]:(fa[x]=get(fa[x]));}

int gcd(int a,int b){

	return b?gcd(b,a%b):a;

}

int main(){

	int x,y,v,xx,yy;

	bool flag=0;

	read(n),read(m);

	for(ri i=1;i<=m;i++){

		read(x),read(y),read(v);

		edge[i].x=x,edge[i].y=y,edge[i].dis=v;

	}

	read(s),read(t);

	sort(edge+1,edge+1+m);

	int mx,cnt=0;

	double mi=inf;

	int fz,fm;

	for(ri i=1;i<=m;i++){

		mx=-inf,flag=0;

		for(ri j=1;j<=n;j++)fa[j]=j;

		for(ri j=i;j<=m;j++){

			x=edge[j].x,y=edge[j].y,v=edge[j].dis;

			xx=get(x),yy=get(y);

			if(xx==yy)continue;

			fa[xx]=yy;

			mx=max(mx,v);

			if(get(s)==get(t)){

				flag=1;break;

			}//if(cnt==n-1)break;

		}

		if(i==1&&get(s)!=get(t)){

			puts("IMPOSSIBLE");

			return 0;

		}

		else if(flag){

			double tmp=(double)mx/edge[i].dis;

			//printf("%d %d %lf\n",mx,edge[i].dis,tmp);

			if(tmp<mi){

				flag=1;

				mi=tmp;

				fm=edge[i].dis,fz=mx;

			}

		}

	}

	int GCD=gcd(fz,fm);

	fm=fm/GCD,fz=fz/GCD;

	if(fm==1)printf("%d\n",fz);

	else printf("%d/%d\n",fz,fm);

	return 0;

}