小澳的葫芦

  我们考虑二分答案。假设答案为mid，选了k条边，权值分别为v1、v2、v3... 那么$\frac{v1+v2+v3...+vk}{k+1}<=mid$ --> $v1+v2+v3...+vk-k\times mid<=mid$ --> $(v1-mid)+(v2-mid)+(v3-mid)...+(vk-mid)<=mid$ 那么也就是二分+spfa，做的时候边权全部-mid，然后跑spfa，跑出来比mid小就，r=mid，否则l=mid ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,cnt=0; int head[2100],nxt[2100],to[2100]; int q[100000],f[2100]; double val[2100],dis[2100]; void addedge(int x,int y,double z) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=z; } double spfa(double x) { memset(dis,0x7f,sizeof(dis)); int l=0,r=1; q[1]=1,dis[1]=0,f[1]=1; while(l<r) { int u=q[++l]; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(dis[v]>dis[u]+val[i]-x) { dis[v]=dis[u]+val[i]-x; if(!f[v]) { q[++r]=v; f[v]=1; } } } f[u]=0; } return dis[n]; } int main() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); } double l=0,r=50000000; while(r-l>1e-5) { double mid=(l+r)/2; if(spfa(mid)<=mid) r=mid; else l=mid; } printf("%.3lf",l); return 0; } ```