开刷图论题
所以为什么上来就这么难aaa
可以证明，当路径为一个简单环(≥2)时，比率最小
是不是只有我这个菜鸡没看清题想了半天为什么是环
证明
二分一个mid使比率为$mid<{\frac {\sum Fi}{\sum Ti}}$
变一下 ${\sum_{i=1}^{n} Fi-Ti*mid}>0$
发现变成了找正环，又不好做，两边同时乘-1转化为找负环
spfa判负环
code
1 #include<bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define int long long 5 #define eps 1e-5 6 const int maxn=1100; 7 inline int read(){ 8 int x=0,f=1;char s=getchar(); 9 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 10 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 11 return f*x; 12 } 13 int n,m; 14 struct edge{ 15 int nxt,to,w; 16 }e[5010]; 17 int head[maxn],cnt,fun[maxn],vis[maxn],num[maxn]; 18 double d[maxn]; 19 inline void add(int from,int to,int w){ 20 e[++cnt].to=to;e[cnt].w=w; 21 e[cnt].nxt=head[from];head[from]=cnt; 22 } 23 bool check(double mid){ 24 queue<int>q; 25 memset(d,0,sizeof(d)); 26 for(int i=1;i<=n;i++){ 27 q.push(i);vis[i]=num[i]=1; 28 } 29 while(!q.empty()){ 30 int x=q.front();q.pop(); 31 vis[x]=0; 32 for(int i=head[x];i;i=e[i].nxt){ 33 int y=e[i].to;double dis=e[i].w; 34 if(d[y]>d[x]+mid*dis-(double)fun[x]){ 35 d[y]=d[x]+mid*dis-(double)fun[x]; 36 if(!vis[y]){ 37 q.push(y);vis[y]=1; 38 if(++num[y]>=n)return 0; 39 } 40 } 41 } 42 } 43 return 1; 44 } 45 int main(){ 46 n=read();m=read(); 47 for(int i=1;i<=n;i++){ 48 fun[i]=read(); 49 } 50 for(int i=1;i<=m;i++){ 51 int u,v,w; 52 u=read();v=read();w=read(); 53 add(u,v,w); 54 } 55 double l=0,r=maxn,mid; 56 while(r-l>eps){ 57 mid=(l+r)/2; 58 if(check(mid))r=mid; 59 else l=mid; 60 } 61 printf("%.2lf",l); 62 return 0; 63 } 64 /* 65 accuse 指责 66 acknowledge 承认 67 accustomed 习惯的 68 acquaintance 熟人 69 */ 70 } 71 signed main(){ 72 gengyf::main(); 73 return 0; 74 }