本文共 1101 字，大约阅读时间需要 3 分钟。

最小化$\frac{A}{B}$

先求一遍最小生成树,设权值为$mst$

现在枚举边$(u,v)$,权值为$w$

如果魔法路在生成树上,$(p_u+p_v)/(mst-w)$

如果魔法路不在生成树上,$(p_u+p_v)/(mst-maxx)$

其中$maxx$是最小生成树上$u->v$的最大边权

#include 
   
    using namespace std;const int maxn=1e6+10;int n,pre[maxn],top,r[maxn],ok[maxn];int fa[1009][20],deep[maxn];double maxx[1009][20];int find(int x){
    return x==pre[x]?x:pre[x]=find(pre[x]);}struct p{
   	int l,r;double w;	bool operator < (const p&tmp )	const{
   		return w
    
     =0;i--)		if( deep[fa[x][i]]>=deep[y] )			{
   			ans = max( ans,maxx[x][i] );			x = fa[x][i];		}	if( x== y)	return ans;	for(int i=16;i>=0;i-- )		if( fa[x][i]!=fa[y][i] )		{
   			ans = max( ans, max( maxx[x][i],maxx[y][i] ));			x=fa[x][i],y=fa[y][i];			}	ans = max( ans,max(maxx[x][0],maxx[y][0] ));	return ans; }double x[maxn],y[maxn];int main(){
   	int t; cin >> t;	while( t-- )	{
   		top=0;		cin >> n;		for(int i=1;i<=n;i++)	cin >> x[i] >> y[i] >> r[i];		for(int i=1;i<=n;i++)		for(int j=1;j
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109387541 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！