P8579 [CoE R5/Stoi2029] 半岛铁盒题目背景为什么这样子 你拉着我 说你有些犹豫怎么这样子 雨还没停 你就撑伞要走已经习惯 不去阻止你 过好一阵子 你就会回来印象中的爱情 好像顶不住那时间——《半岛铁盒》题目描述题意简述给定一个n nn个顶点m mm条边的无向图可能有重边自环可能不连通。初始时每个顶点有点权点权为随机正实数。现在需要重新分配每个顶点的点权使得相邻顶点的点权中较大者与较小者之比不超过x xx点权总和不变每个顶点的点权不小于初始时的p q \dfrac{p}{q}qp​。求最小的x ≥ 1 x \ge 1x≥1使得对于给定的图无论初始点权如何均存在一种满足上述要求的重新分配方式。原版题面神在半岛铁盒里创建了一个世界。这个世界由n nn个地域和地域之间的m mm条通道组成每条通道连接两个地域。创世时每个地域有一定的气压气压为正数。由于世界刚刚创建比较混乱所以两个地域之间可能有多条通道相连一个地域也有可能有通道连接到自身两个地域也可能无法通过若干条通道相互通行。由于通道连接的两个地域气压之比大比小下同过大时会在通道里形成强风使得跨地域旅行非常危险所以造世神决定调整每个地域的气压使得每条通道连接的两个地域气压之比都不超过安全比值x xx。显然x ≥ 1 x \ge 1x≥1。由于各种守恒定律被打破会很麻烦所以神希望调整前后所有地域的气压之和不变。由于世界中的生物无法在过低的气压中生存但对高气压的适应力强因此每个地域改变后的气压必须不低于初始的p q \dfrac{p}{q}qp​。由于创世时气压不受神控制地随机所以神希望安全比值x xx满足无论初始气压如何都存在一种合适的调整气压的方法。由于通道越宽敞通行越舒适但是安全比值x xx也越小因此神想要求出满足要求的最小安全比值x xx。由于神忙着处理创世事务所以他钦定你来解决这个问题。输入格式第一行四个正整数n , m , p , q n,m,p,qn,m,p,q含义如题。接下来m mm行每行两个正整数u , v u,vu,v表示一条通道连接的两个地域的编号。输出格式输出一个实数表示x xx的最小值保留7 77位小数。本题采用 Special Judge如果你的答案与参考答案的差值不超过参考答案值的10 − 4 10^{-4}10−4倍即为通过。输入输出样例 #1输入 #13 2 1 2 1 2 2 3输出 #12.0000000输入输出样例 #2输入 #210 20 13 37 1 2 1 3 1 5 2 4 2 5 2 6 3 4 3 5 3 7 3 9 3 10 4 6 4 7 4 8 5 7 5 9 7 8 7 9 7 10 9 10输出 #23.6903390说明/提示数据范围对于10 % 10\%10%的数据n p ≤ q np \le qnp≤q对于另外20 % 20\%20%的数据有一个地域和其他所有地域之间有通道相连对于另外30 % 30\%30%的数据通道构成一棵树。对于100 % 100\%100%的数据1 ≤ u , v ≤ n ≤ 10 3 1 \le u,v \le n \le 10^31≤u,v≤n≤1031 ≤ m ≤ 3 × 10 4 1 \le m \le 3 \times 10^41≤m≤3×1041 ≤ p q ≤ 10 7 1 \le pq \le 10^71≤pq≤107。C实现#includecstdio#definergregister#definelllonglong#definedblongdoubleintn,m,p,q,u,v,d;inthead[1003],cnt;intdep[1003],que[1003],hd,tl;structedge{intnxt,to;}e[60007];inlinevoidadd(intx,inty){e[cnt].nxthead[x],e[cnt].toy,head[x]cnt;e[cnt].nxthead[y],e[cnt].tox,head[y]cnt;}ll a[1003];inlinevoidbfs(ints){que[tl]s,dep[s]0;while(hdtl){uque[hd],a[dep[u]],hd;for(rgintihead[u];i;ie[i].nxt){ve[i].to;if(~dep[v])continue;que[tl]v,dep[v]dep[u]1;}}ddep[u];}inlinedbcalc(db x){db resa[d];for(rgintid-1;~i;--i)resres/xa[i];returnres;}inlinedbsolve(){db l1,r1e10,md,rs,tp;for(rginti0;id;i)a[i]*p;while(r-l1e-8){md(lr)/2,rs-q,tp1;for(rginti0;id;i){rsa[i]*tp,tp/md;}if(rs0)lmd;elsermd;}returnl;}db x,y;intmain(){scanf( %d %d %d %d,n,m,p,q);x1;if(n*pq)returnputs(1.0000000),0;for(rginti0;im;i){scanf( %d %d,u,v);if(u!v)add(u,v);}for(rginti1;in;i){for(rgintj0;jn;j)dep[j]-1,a[j]0;hd1,tl0,bfs(i),ysolve();if(yx)xy;}printf(%.7Lf\n,x);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容