圣玛格丽特大图书馆是一座由石材砌成的角柱型高塔，是欧洲屈指可数的巨大书库。图书馆整面墙壁都是巨大的书架，书架与书架之间就像巨大的迷宫一般，以细窄的木制楼梯连结。大图书馆的最高处是一个绿意盎然的植物园，维多利加正在那无聊地看着书。今天，一如往常地，久城要爬上这迷宫般的楼梯给维多利加送讲义。
图书馆墙壁上有N个平台，编号为1到N，入口为1号，植物园为N号。有M个连接两个不同平台的楼梯，爬每个楼梯需要消耗一定的体力值。楼梯一定是由低处通往高处的，为了省时间，久城只能选择上楼梯而不能下楼梯，也就是说，楼梯之间不会形成环路。而且，出于人性化考虑，不管久城选择哪条路线上楼，他爬的楼梯数量一定小于20。
为了使体力消耗尽量平稳，久城需要选择一条“每个楼梯消耗体力值的方差最小”的路径上楼。请帮助久城计算出这个最小方差。
方差公式：nθ=Σxi^2-(Σxi)^2/n
先拓扑排序，f[i][j][k]表示走到i，走了j步，走的长度为k时候的最小方差，让后直接O(N*S*K)dp，细节非常繁琐，要注意各种double问题
#pragma GCC optimize("O3")#pragma G++ optimize("O3")#include #include #include #include using namespace std;int n,m,h[60],cnt=0,d[60],r[60],t=0;double f[61][61][1110],A=1e10;struct edge{ int v,c,nt; } G[500]; queue q;inline void gmin(double& a,double b){ a>b?a=b:0; }int main(){ freopen("library.in","r",stdin); freopen("library.out","w",stdout); scanf("%d%d",&n,&m); for(int x,y,c;m--;){ scanf("%d%d%d",&x,&y,&c); ++d[y]; G[++cnt]=(edge){y,c,h[x]}; h[x]=cnt; } for(int i=1;i<=n;++i) if(!d[i]) q.push(i); while(!q.empty()){ r[++t]=q.front(); q.pop(); for(int i=h[r[t]];i;i=G[i].nt) if(--d[G[i].v]==0) q.push(G[i].v); } memset(f,127,sizeof f); f[1][0][0]=0; for(int i,I=1;I =0) gmin(A,f[n][j][k]/j); printf("%.4lf\n",A);}