链接
https://www.acwing.com/problem/content/363/
题目
给定一张L个点、P条边的有向图，每个点都有一个权值f[i]，每条边都有一个权值t[i]。
求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。
输出这个最大值。
注意：数据保证至少存在一个环。
输入格式
第一行包含两个整数L和P。
接下来L行每行一个整数，表示f[i]。
再接下来P行，每行三个整数a，b，t[i]，表示点a和b之间存在一条边，边的权值为t[i]。
输出格式
输出一个数表示结果，保留两位小数。
数据范围
(2≤L≤1000,)
(2≤P≤5000,)
(1≤f[i],t[i]≤1000)
输入样例：
5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2
输出样例：
6.00
思路
答案求一个环上(frac {sum_{i=1}^jf[i]}{sum_{i=1}^jt[i]})的最大值，那么可以通过二分枚举这个值k，如果存在答案大于等于k，那么有(sum_{i=1}^jf[i]≤k*sum_{i=1}^jt[i])，我们令每条边从u到v的边权等于(k*t[i]-f[u]),判断是否满足不等式，就相当于在这样的一个图中判断是否存在负环。
由于是在整合图中求，所以spfa开始把所有点加入队列中。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=5010;
int h[N],e[M],nex[M],f[N],q[N],idx,n,m,cnt[N];
double d[N],w[M];
bool st[N];
void add(int u,int v,int t){
e[idx]=v;
w[idx]=t;
nex[idx]=h[u];
h[u]=idx++;
}
bool spfa(double k){
int hh=0,tt=0;
for(int i=1;i<=n;++i){
q[tt++]=i;
st[i]=1;
d[i]=0;
cnt[i]=0;
}
while(hh!=tt){
int u=q[hh++];
if(hh==N) hh=0;
st[u]=0;
for(int i=h[u];~i;i=nex[i]){
int v=e[i];
//cout<<u<<":"<<v<<endl;
//cout<<d[u]+k*w[i]-f[u]<<endl;
if(d[v]>d[u]+k*w[i]-f[u]){
//cout<<"in
";
d[v]=d[u]+k*w[i]-f[u];
cnt[v]=cnt[u]+1;
if(cnt[v]==n) return true;
if(!st[v]){
q[tt++]=v;
if(tt==N) tt=0;
st[v]=1;
}
}
}
}
return false;
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>f[i];
}
for(int i=1;i<=m;++i){
int x,y,t;
cin>>x>>y>>t;
add(x,y,t);
}
double l=0,r=1000,ans=-1;
for(int i=1;i<=100;++i){
double mid=(l+r)/2.0;
if(spfa(mid)){
l=mid;
ans=mid;
}
else r=mid;
}
printf("%.2f",ans);
return 0;
}