一类特殊有向图上的最大比率环
cxyMOI
·
·
算法·理论
关于一类有向图上的最大比率环
给定正整数 n 和 m 满足 m<2^n，如下构造一个带边权的有向图：
图中含有 2^n 个节点，编号为 0,1,2,...,2^n-1。对任意 1\le i<2^n，从 i 号点向 2i\bmod 2^n 号点连一条权值为 0 的边（这样形成一颗满二叉树加上 2^{n-1}\to0 的边）；对任意 0\le i<2^n，若 i\mathop{\mathrm{and}}m=0（其中 \mathop{\mathrm{and}} 表示按位与），则从 i 号点向 2i+1\bmod 2^n 号点连一条边权为 1 的边。由于 m 是正整数，图上一定不存在自环。
问图上的最大比率环的比率。
假设给出的是 m 的二进制表示中 1 的全部位置，并且可以 O(1) 计算 O(\log m) 大小的整数之间的运算。
$\mathrm{popcount}(m)=3$ 时或许存在 $O(1)$ 算法。例如可以证明，$m=3+2^{a-1}$（$a\ge 3$）时答案为$\begin{cases}\frac{1}{3}&3\nmid a\\\frac{a}{3a+3}&3\mid a\end{cases}$。
最大比率环的一般算法是 $O(|V||E|)=O(m^2)$ 的。问：
有没有复杂度低于 $O(m^2)$ 的算法？
进一步地，有没有关于 $\mathrm{popcount}(m)$ 多项式时间复杂度的算法？
下面是一个可以（在大约半分钟内）计算任何一个 $m<2^{25}$ 的情况程序，可以用来找规律。
```
#include <iostream>
#include <assert.h>
#include <chrono>
#include <cstring>
using ll=long long;
using ui=unsigned int;
const ui N=1<<25;
ui m=0;
ui stk[N],pre[N],ct[N];
ll dis[N];
bool vis[N],t[N];
bool check(const ui n,const ll l,const ll r){
for(ui i=0;i<n;i++){
stk[i]=i^(n-1);
}
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(t,0,sizeof(t));
memset(ct,0,sizeof(ct));
memset(pre,-1,sizeof(pre));
ui sz=n;
while(sz>0){
ui u=stk[--sz];
vis[u]=1;
t[u]=1;
ui v=(2*u)&(n-1);
if(dis[v]>=dis[u]+l){
if(t[v]){
return 1;
}
dis[v]=dis[u]+l;
if(vis[v]){
stk[sz++]=v;
vis[v]=0;
pre[v]=u;
ct[u]++;
}
}
if((u&m)==0){
v=(2*u+1)&(n-1);
if(dis[v]>=dis[u]+r){
if(t[v]){
return 1;
}
dis[v]=dis[u]+r;
if(vis[v]){
stk[sz++]=v;
vis[v]=0;
pre[v]=u;
ct[u]++;
}
}
}
while(ct[u]==0){
t[u]=0;
u=pre[u];
if(u==-1){
break;
}
ct[u]--;
}
}
return 0;
}
int main(){
int x,y,z;//假设计算 popcount(m)=3 的情况
std::cin>>x>>y>>z;
assert(0<x&&x<y&&y<z&&z<26);
auto start=std::chrono::high_resolution_clock::now();
m=(1<<(x-1))+(1<<(y-1))+(1<<(z-1));
ui n=1<<z;
ll R=z<<z;
ui l=0,r=R;
while(l+1<r){
ll mid=(l+r)/2;
if(check(n,mid,mid-R)){
l=mid;
}else{
r=mid;
}
std::cout<<r-l<<std::endl;
}
ll p=1;
while(1){
ll q=p*R/l;
if(q*(l+1)>R*p){
std::cout<<p<<'/'<<q<<std::endl;
break;
}
p++;
}
auto end=std::chrono::high_resolution_clock::now();
std::chrono::duration<double> t=end-start;
std::cout<<"Time: "<<t.count()<<" seconds"<<std::endl;
return 0;
}
```