【题解】P8579 [CoE R5/Stoi2029] 半岛铁盒

[CoE R5/Stoi2029] 半岛铁盒

题目背景

为什么这样子 你拉着我 说你有些犹豫
怎么这样子 雨还没停 你就撑伞要走
已经习惯 不去阻止你 过好一阵子 你就会回来
印象中的爱情 好像顶不住那时间
——《半岛铁盒》

题目描述

题意简述

给定一个 $n$ 个顶点 $m$ 条边的无向图，可能有重边自环，可能不连通。

初始时每个顶点有点权，点权为随机正实数。现在需要重新分配每个顶点的点权，使得：

1. 相邻顶点的点权中较大者与较小者之比不超过 $x$；
2. 点权总和不变；
3. 每个顶点的点权不小于初始时的 $\frac{p}{q}$。

求最小的 $x\ge 1$，使得对于给定的图，无论初始点权如何，均存在一种满足上述要求的重新分配方式。

原版题面

神在半岛铁盒里创建了一个世界。

这个世界由 $n$ 个地域和地域之间的 $m$ 条通道组成，每条通道连接两个地域。创世时每个地域有一定的气压，气压为正数。

由于世界刚刚创建，比较混乱，所以两个地域之间可能有多条通道相连，一个地域也有可能有通道连接到自身，两个地域也可能无法通过若干条通道相互通行。

由于通道连接的两个地域气压之比（大比小，下同）过大时会在通道里形成强风，使得跨地域旅行非常危险，所以造世神决定调整每个地域的气压使得每条通道连接的两个地域气压之比都不超过安全比值 $x$。显然 $x\ge 1$。

由于各种守恒定律被打破会很麻烦，所以神希望调整前后所有地域的气压之和不变。

由于世界中的生物无法在过低的气压中生存但对高气压的适应力强，因此每个地域改变后的气压必须不低于初始的 $\frac{p}{q}$。

由于创世时气压不受神控制地随机，所以神希望安全比值 $x$ 满足无论初始气压如何都存在一种合适的调整气压的方法。

由于通道越宽敞，通行越舒适，但是安全比值 $x$ 也越小，因此神想要求出满足要求的最小安全比值 $x$。

由于神忙着处理创世事务，所以他钦定你来解决这个问题。

输入格式

第一行四个正整数 $n,m,p,q$，含义如题。

接下来 $m$ 行，每行两个正整数 $u,v$ 表示一条通道连接的两个地域的编号。

输出格式

输出一个实数表示 $x$ 的最小值，保留 $7$ 位小数。

本题采用 Special Judge，如果你的答案与参考答案的差值不超过参考答案值的 $10^{-4}$ 倍即为通过。

样例

样例输入 #1

3 2 1 2
1 2
2 3
1
2
3

样例输出 #1

2.0000000
1

样例输入 #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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

样例输出 #2

3.6903390
1

提示

数据范围

对于 $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$。

思路

事实上我们可以把气压看作可以为非负数，然后令 $y=\frac{1}{x}$，将条件改为小比大 $\ge y$。

发现重边和自环没有影响，直接忽略。图不连通时相当于对每个连通图单独处理后取最大值，实现方式完全相同。

称一个状态为 ${\mathbb{R}}_{\ge 0}^n$ 中的一个向量，其中第 $i$ 维的值为地域 $i$ 的气压。

首先显然有一个结论：若对于两个状态能够做到，那么对于它们的和也能够做到。

从而若要对任意的状态均能够做到，那么只需要对于只有一维不为 $0$ 的状态能够做到。由于每维扩倍没有本质影响，所以相当于只有一维为 $1$ 其余维为 $0$ 时能够做到。

以下考虑如何解决一维为 $1$ 其余维为 $0$ 的情况。首先显然 $\frac{p}{q}$ 的限制只对初始气压为 $1$ 的点（设为 $u$）有影响。要使调整后 $u$ 点的气压足够大，则必须要其他点调整后的气压尽量小。显然直接和 $u$ 相连的点的气压至少是 $y$，从而与 $u$ 距离为 $2$ 的点的气压至少是 $y^2$，依此类推，最终我们得到一个不等式：
$$\sum _{d\ge 0}{a}_d{y}^d\le \frac{q}{p},$$

其中 $a_d$ 表示与 $u$ 距离为 $d$ 的点数，特别地有 $a_0=1$。

由于左边是关于 $y$ 单调递增的，所以可以二分。由于 $y=0$ 时左边小于右边，所以必然有解。发现 $np\le q$ 时任意 $y$ 均满足条件，故答案即为 $1$。

如果有一个点和其他点均有连边的话，那么容易证明只有这个点的点权为 $1$ 是极端情况，我们只要解 $(n-1)y+1\le \frac{q}{p}$ 就可以了。

如果是树的话，搜起来会方便一点（？

正解：对每个点 $u$ 进行一次 $\text{DFS}$ 或 $\text{BFS}$ 得到 $a$ 数组，然后二分答案即可，时间复杂度 $O(n(m+n\log s))$，$s$ 即精度要求。

Code

#include
#define rg register
#define ll long long
#define db long double
int n,m,p,q,u,v,d;
int head[1003],cnt;
int dep[1003],que[1003],hd,tl;
struct edge
{
    int nxt,to;
}e[60007];
inline void add(int x,int y)
{
    e[++cnt].nxt=head[x],e[cnt].to=y,head[x]=cnt;
    e[++cnt].nxt=head[y],e[cnt].to=x,head[y]=cnt;
}
ll a[1003];
inline void bfs(int s)
{
    que[++tl]=s,dep[s]=0;
    while(hd<=tl)
    {
        u=que[hd],++a[dep[u]],++hd;
        for(rg int i=head[u];i;i=e[i].nxt)
        {
            v=e[i].to;if(~dep[v])continue;
            que[++tl]=v,dep[v]=dep[u]+1;
        }
    }
    d=dep[u];
}
inline db calc(db x)
{
    db res=a[d];
    for(rg int i=d-1;~i;--i)res=res/x+a[i];
    return res;
}
inline db solve()
{
    db l=1,r=1e10,md,rs,tp;
    for(rg int i=0;i<=d;++i)a[i]*=p;
    while(r-l>=1e-8)
    {
        md=(l+r)/2,rs=-q,tp=1;
        for(rg int i=0;i<=d;++i)
        {
            rs+=a[i]*tp,tp/=md;
        }
        if(rs>0)l=md;
        else r=md;
    }
    return l;
}
db x,y;
int main()
{
    scanf(" %d %d %d %d",&n,&m,&p,&q);x=1;
    if(n*p<=q)return puts("1.0000000"),0;
    for(rg int i=0;i<m;++i){scanf(" %d %d",&u,&v);if(u!=v)add(u,v);}
    for(rg int i=1;i<=n;++i)
    {
        for(rg int j=0;j<=n;++j)dep[j]=-1,a[j]=0;
        hd=1,tl=0,bfs(i),y=solve();if(y>x)x=y;
    }
    printf("%.7Lf\n",x);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

AD

$$\text{Lvshu OJ }\text{，大量高质量题目等着你，点击这里马上注册。}$$

$$\text{Lvshu OS}\text{，崭新的系统，点击这里，马上查看详情}$$