P8579 [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

输入 #1

3 2 1 2
1 2
2 3

输出 #1

2.0000000

输入输出样例 #2

输入 #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

输出 #2

3.6903390

说明/提示

数据范围

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

C++实现

#include<cstdio>
#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;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容