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

找一个环,最大化$\frac{\sum va{l}_i}{\sum cos{t}_i}$

其中$va{l}_i$为点权,$cos{t}_i$为边权

令$r=\frac{\sum va{l}_i}{\sum cos{t}_i}$

有$r\ast \sum cos{t}_i-\sum va{l}_i=0$

设函数$f(r)=r\ast \sum cos{t}_i-\sum va{l}_i$

显然对于不同的环对应的直线也不同,但是$r$始终是正数

如图所示,不同的环对应不同的直线,二那些与$x$轴的交点就是我们的合法值

所以二分一个$mid$,作直线$x=mid$交直线若干点

若存在直线交点是负数,说明最大值还在右边

若所有交点都是正数,说明最大值在左边

现在任务变成了判断是否所有的交点都是正数,所以求最小值即可

不过这个问题比较特殊,我们选的集合是有限定的,必须是一个环

所以想象一下把每个点拆点成两个,彼此连一条$-va{l}_i$的边,图中原来的边变成$r\ast cos{t}_i$

所以直接跑最短路判断有没有负环即可,更方便了

#include 
   
    #include 
    
     #include 
     
      using namespace std;const double eps=1e-7;const int maxn = 2e5+10;double p[maxn],dis[maxn];int num[maxn],n,m,vis[maxn];struct edge{
   	int to,nxt; double w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,double w){
   	d[++cnt] = (edge){
   v,head[u],w},head[u]=cnt;}bool spfa(double mid){
   	queue
      
       q;	for(int i=0;i<=n;i++)	dis[i]=1e9,vis[i]=num[i]=0;	q.push( 1 ); num[1]++; dis[1]=0;	while( !q.empty() )	{
   		int u = q.front(); q.pop();		vis[u]=0;		for(int i=head[u];i;i=d[i].nxt )		{
   			int v=d[i].to;			double val = mid*d[i].w-p[v];			if( dis[u]+val+eps
       
        > n >> m )	{
   		for(int i=1;i<=n;i++)	scanf("%lf",&p[i]);		for(int i=1;i<=m;i++)		{
   			int l,r; double w; scanf("%d%d%lf",&l,&r,&w);			add(l,r,w);		}		double l=0,r=10000,ans=0;		while( r>=l+eps )		{
   			double mid = (l+r)/2.0;			if( spfa(mid) )	ans = mid,l = mid+eps;			else	r = mid-eps;		}		printf("%.2f\n",l);		cnt=1;		for(int i=0;i<=n;i++)	head[i]=0;	}}
       
      
     
    
   

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