[CoE R5/Stoi2029] 半岛铁盒

Luogu

IDLGP8579

Time1000ms

Memory128MB

DifficultyP4

数学图论二分洛谷原创Special JudgeO2优化洛谷月赛2029

**题意简述** 给定一个 $n$ 个顶点 $m$ 条边的无向图，可能有重边自环，可能不连通。初始时每个顶点有点权，点权为随机正实数。现在需要重新分配每个顶点的点权，使得： 1. 相邻顶点的点权中较大者与较小者之比不超过 $x$； 2. 点权总和不变； 3. 每个顶点的点权不小于初始时的 $\dfrac{p}{q}$。求最小的 $x \ge 1$，使得对于给定的图，无论初始点权如何，均存在一种满足上述要求的重新分配方式。 --- **原版题面** 神在半岛铁盒里创建了一个世界。这个世界由 $n$ 个地域和地域之间的 $m$ 条通道组成，每条通道连接两个地域。创世时每个地域有一定的气压，气压为正数。由于世界刚刚创建，比较混乱，所以两个地域之间可能有多条通道相连，一个地域也有可能有通道连接到自身，两个地域也可能无法通过若干条通道相互通行。由于通道连接的两个地域气压之比（大比小，下同）过大时会在通道里形成强风，使得跨地域旅行非常危险，所以造世神决定调整每个地域的气压使得每条通道连接的两个地域气压之比都不超过安全比值 $x$。显然 $x \ge 1$。由于各种守恒定律被打破会很麻烦，所以神希望调整前后所有地域的气压之和不变。由于世界中的生物无法在过低的气压中生存但对高气压的适应力强，因此每个地域改变后的气压必须不低于初始的 $\dfrac{p}{q}$。由于创世时气压不受神控制地随机，所以神希望安全比值 $x$ 满足无论初始气压如何都存在一种合适的调整气压的方法。由于通道越宽敞，通行越舒适，但是安全比值 $x$ 也越小，因此神想要求出满足要求的最小安全比值 $x$。由于神忙着处理创世事务，所以他钦定你来解决这个问题。 ## Input 第一行四个正整数 $n,m,p,q$，含义如题。接下来 $m$ 行，每行两个正整数 $u,v$ 表示一条通道连接的两个地域的编号。 ## Output 输出一个实数表示 $x$ 的最小值，保留 $7$ 位小数。本题采用 Special Judge，如果你的答案与参考答案的差值不超过参考答案值的 $10^{-4}$ 倍即为通过。 [samples] ## Background > 为什么这样子你拉着我说你有些犹豫 > 怎么这样子雨还没停你就撑伞要走 > 已经习惯不去阻止你过好一阵子你就会回来 > 印象中的爱情好像顶不住那时间 > ——《[半岛铁盒](https://www.bilibili.com/video/BV1fx411N7bU?p=26)》 ## Note **数据范围** 对于 $10\%$ 的数据，$np \le q$；对于另外 $20\%$ 的数据，有一个地域和其他所有地域之间有通道相连；对于另外 $30\%$ 的数据，通道构成一棵树。对于 $100\%$ 的数据，$1 \le u,v \le n \le 10^3$，$1 \le m \le 3 \times 10^4$，$1 \le p<q \le 10^7$。

Samples

Input #1

3 2 1 2
1 2
2 3

Output #1

2.0000000

Input #2

10 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

Output #2

3.6903390

API Response (JSON)

{
  "problem": {
    "name": "[CoE R5/Stoi2029] 半岛铁盒",
    "description": {
      "content": "**题意简述** 给定一个 $n$ 个顶点 $m$ 条边的无向图，可能有重边自环，可能不连通。 初始时每个顶点有点权，点权为随机正实数。现在需要重新分配每个顶点的点权，使得： 1. 相邻顶点的点权中较大者与较小者之比不超过 $x$； 2. 点权总和不变； 3. 每个顶点的点权不小于初始时的 $\\dfrac{p}{q}$。 求最小的 $x \\ge 1$，使得对于给定的图，无论初始点权如何",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8579"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题意简述**\n\n给定一个 $n$ 个顶点 $m$ 条边的无向图，可能有重边自环，可能不连通。\n\n初始时每个顶点有点权，点权为随机正实数。现在需要重新分配每个顶点的点权，使得：\n\n1. 相邻顶点的点权中较大者与较小者之比不超过 $x$；\n\n2. 点权总和不变；\n\n3. 每个顶点的点权不小于初始时的 $\\dfrac{p}{q}$。\n\n求最小的 $x \\ge 1$，使得对于给定的图，无论初始点权如何...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments