P8579sol

· · 题解

简要题意：

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

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

  1. 相邻顶点的点权中较大者与较小者之比不超过 x；

  2. 点权总和不变；

  3. 每个顶点的点权不小于初始时的 \dfrac{p}{q}。

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

思路

求的是最小，所以只考虑最劣的情况。

容易发现最劣的情况就是，一个源点的权值为无穷大（10^9），其他的近似于 0。（干脆直接取 0）

为什么这是对的呢？感性理解一下，如果这张图再增加任何一个还有值的源点，此时就有两个源点共同分担同一个安全系数，这明显是比我们给出的图要优的，所以不能取。

考虑枚举源点。

再考虑安全系数，容易发现，安全系数是具有单调性的，如果相邻顶点的点权中较大者与较小者之比不超过 x，那么这个比也一定不会超过任何比 x 要大的数。

然后就可以二分安全系数 x，考虑 check 怎么写。

容易发现，只要让相邻的点的比刚好卡在 x 上就一定是对的，否则的话会让源点分出去更多的权值，反而不优。

这样直接根据这个思路直接 bfs 判答案，时间复杂度 O(60n(n+m))，这个 60 是二分的常数。

然后你发现过不了，被卡成 80 分了，原因是 n\leqslant10^3,m\leqslant3\times10^4，而 60nm 卡到极限情况需要枚 1800000000 次，相当于 18 秒，非常低级，考虑怎么优化。

我们发现根本没必要每次二分都 bfs，因为对于同一个源点每次 bfs 出来的搜索顺序是一样的，我们考虑先把搜索顺序搜出来，然后按照搜索顺序直接 dp，这样一次时间复杂度是 O(n) 的，于是这个题时间复杂度被优化成了 O(n(n+m)+60n^2)，可以通过。

卡得很恶心

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,p,q;
double F;
int cnt;
int head[60005];
int nxt[60005];
int edge[60005];
void addedge(int u,int v){
   cnt++;
   nxt[cnt]=head[u];
   head[u]=cnt;
   edge[cnt]=v;
   return;
}
double ans=0;
double D[1005];
bool vis[1005];
int dep[1005];
inline void bfs(int S){
   for(int i=1;i<=n;i++){
      dep[i]=0;
      vis[i]=false;
   }
   queue<int> q;
   q.push(S);
   vis[S]=true;
   dep[S]=1;//dep表示搜索顺序
   while(!q.empty()){
      int t=q.front();
      q.pop();
      for(int i=head[t];i;i=nxt[i]){
         int v=edge[i];
         if(vis[v])continue;
         vis[v]=true;
         dep[v]=dep[t]+1;
         q.push(v);
      }
   }
   return ;
}
bool check(double x){
   double sum=1.*(q-p)/q;//sum表示我可以分出去的最多的权值
   D[0]=0;
   D[1]=1.*p/q;//D[i]表示我在dep为i的点中需要花费的权值大小
   for(int i=1;i<=n;i++){
      if(!dep[i])continue;
      if(dep[i]==1)continue;
      D[dep[i]]=D[dep[i]-1]/x;//由我前一个深度转移下来
      sum-=D[dep[i]];//分出权值
   }
   return sum>=0.;//如果还有权值剩余就说明成功了
}
signed main(){
   scanf("%lld%lld%lld%lld",&n,&m,&p,&q);
   F=1.*p/q;
   for(int i=1;i<=m;i++){
      int u,v;
      scanf("%lld%lld",&u,&v);
      addedge(u,v);
      addedge(v,u);
   }
   for(int i=1;i<=n;i++){//i号点为无穷大
      bfs(i);//求dep
      sort(dep+1,dep+1+n);//为了方便dp
      double lt=1-(1e-7),rt=3e9+1e-7;//二分上下界，我不会算，所以开大点
      int cnt=60;//控制二分次数，不这样会有精度问题
      while(cnt--){
         double mid=(lt+rt)/2;
         if(check(mid)){
            rt=mid;
         }
         else{
            lt=mid;
         }
      }
      ans=max(ans,rt);
   }
   printf("%.7lf",ans);
   return 0;
}