企业微网站与手机微信/深圳企业黄页网

天路

求一个环最大化$\frac{\sum v_i}{\sum c_i}$

按照$01$分数规划的基本套路来…

$f(r)=\sum v_i-r\ast \sum c_i$

对于不同的环对应不同的直线,但斜率始终小于$0$

所以二分一个$mid$,作直线$x=mid$,交上述直线一些点

若存在点的$y$座标大于$0$说明最大值在右边

否则最大值在左边

于是把每条边的权值看作$v_i-r\ast c_i$

只需要判断是否存在环的权值大于$0$即可

假设我们设的函数是

$f(r)=r\ast \sum c_i-\sum v_i$

那么斜率大于零,同样作$x=mid$

此时若存在$y$坐标小于零的交点说明最大值还在右边

所以如果把边权看作$r\ast c_i-v_i$只需要判断是否存在负权环即可

但是这题需要用改进的$spfa$才不会超时

我只有$90$分…

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=4e5+10;
const int inf=1e16;
const double eps=1e-3;
struct edge{int to,nxt; double v,c;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,double vv,double c)
{d[++cnt]=(edge){v,head[u],vv,c},head[u]=cnt;
}
double dis[maxn];
int num[maxn],n,m,vis[maxn];
bool spfa(double mid)
{for(int i=1;i<=n;i++)	dis[i]=inf,num[i]=0,vis[i]=0;num[0]=1; dis[0]=0;queue<int>q; q.push(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 w = d[i].c*mid-d[i].v;if( dis[v]>dis[u]+eps+w ){dis[v]=dis[u]+w;if( !vis[v] ){vis[v]=1,q.push(v);num[v]++;if( num[v]>=n )	return true;}}}}return false;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i=1;i<=m;i++){int l,r; double v,c;cin >> l >> r >> v >> c;add(l,r,v,c); }for(int i=1;i<=n;i++)	add(0,i,0,0); double l=0,r=209,ans=-1;while( r>=l+eps ){double mid = (l+r)/2.0;if( spfa(mid) )	ans=mid,l=mid+eps;else	r=mid-eps;}if( ans==-1 )	cout << -1;else	printf("%.1lf",ans);
}