P1576

2021CHD · 2025-05-24 07:59:26 · 题解

题目大意

有 n 个节点与 m 条带权双向边 e_i=((x_i,y_i),z_i)，求解从节点 A 到节点 B 的路径权值的最小值（四舍五入到小数点后第八位），保证节点 A 与节点 B 连通。路径 P 的权值定义为 100\prod_{e_i\in P}\frac{100}{(100-z_i)}。

• n\le2000$，$m\le10^5

解法 0（错解）

观察到原问题为单源最短路形式，于是可以使用 dijkstra 算法解决，需要注意本题的松弛操作较为特殊。

关于 dijkstra 算法，本题解不再过多赘述，请参见 OI Wiki。

这是我的 AC 记录。（无法通过 hack 数据）

解法 1（正确性模糊）

问题就在于本题其实没有限制答案的大小，也就是说答案可能非常巨大，比如以下 hack 数据：

input：

20 19
1 2 30
2 3 99
3 4 99
4 5 99
5 6 99
6 7 99
7 8 99
8 9 99
9 10 99
10 11 99
11 12 99
12 13 99
13 14 99
14 15 99
15 16 99
16 17 99
17 18 99
18 19 99
19 20 99
1 20

output：

142857142857142857142857142857142857142.85714286

这里有更多的 hack 数据。

不难留意到答案显然已经大到需要使用高精度的程度，于是考虑给上述算法加上高精度。（我从未见过哪种语言的实数类型会自带高精度的）

具体地可以发现到每个点的距离都是 \frac{100^n}{dis_i} 的形式（其中 dis_i 为整数），于是直接用高精度维护距离的分母即可。

于是本题就愉快地解决了……吗？

分析时间复杂度，由于答案的位数最大可达到 O(n) 级别，于是复杂度来到了 O(n^3)，即便加上高精度压位也未必能通过本题。

不难发现复杂度瓶颈来自需要 O(n^2) 次高精度大小对比的“找到距离最小的节点”这一步，其余复杂度为 O(nm)，压位以后复杂度可以接受，那么有两个优化方向：

1. 减少对比的次数。
2. 减少单次对比所需的时间。

对于第一种方向，不难发现即使使用二叉堆优化 dijkstra 也需要 O(m\log n) 次对比操作，复杂度比较危险，于是可以考虑第二种方向。

不难发现本题中的 dis_i 的所有质因子均不超过 100，由于这类数比较稀疏，于是我们大胆猜想：只需比较最高若干位即可确定两数是否相等。

事实上，数学上有 abc 猜想，叙述如下：

• 对正整数 x 定义 f(x) 为 x 的所有不同质因子的乘积，如 f(60)=30。
• 对于任意正实数 \epsilon，只有有限正整数三元组 (a,b,c) 满足 a+b=c，\gcd(a,b)=1 且 c>f(abc)^{1+\epsilon}。

有数学家在 2012 年对该猜想提出证明，但至今仍未确认其正确性。

对于本题，我们想构造两个质因子都不超过 100 的大数 a,c 相差为 b，并且让 \frac{\ln a}{\ln b} 尽可能大，由于 \gcd(a,c)>1 的情形与 \gcd(a,c)=1 的情形的 \frac{\ln a}{\ln b} 的值是没有区别的，于是在猜想的适用范围。

由于本涉及的数巨大，而 f(abc)\le2\times3\times5\times\dots\times97b=2305567963945518424753102147331756070b，而 c 的值仅为 f(abc)^{1+\epsilon}，故我们可以估计 b 的数量级与 c 的数量级相差不大，实际写代码时，对高精度数的大小比对最高的 320 位就完全无法构造 hack 数据了。（如果真的有人构造出了 hack 数据请私信联系我）

这是我的 AC 记录。

解法 2（正确性有保证）

上面那种做法的正确性模糊，然而数学猜想的存在又表明 hack 数据的构造是困难的，于是我们应当考虑另外一个方向：减少对比的次数。

我们已经说过，使用二叉堆优化的 dijkstra 在本题中的复杂度为 O(nm\log n)，正确性模糊。（然而 hack 数据的构造是困难的）于是我们可以考虑使用更快速的堆。

配对堆拥有比二叉堆更优的复杂度，在本题中为 O(2^{2\sqrt{\log\log n}}nm) 与 \Omega(nm\log\log n) 的，然而其偏大的常数使其表现与二叉堆并无太大区别，这里，我们介绍斐波那契堆。

值得一提的是 Brodal queue 与斐波那契堆复杂度相同，且去除了均摊的过程，但由于其常数很大并且过于繁琐，不在这里介绍。其实就是我不会。

以小根堆为例，斐波那契堆可以做到均摊 O(1) 插入节点，均摊 O(1) 减小节点值以及均摊 O(\log n) 删除最小节点，当然查询最小值是 O(1) 的。（作为可并堆，它还支持 O(1) 合并，但是本题无需执行合并操作）

斐波那契堆维护了一个森林，其中每个节点的子节点个数都是 O(\log n) 级别的。（树高对斐波那契堆的复杂度没有影响）

如图为一个合法的斐波那契堆：（以小根堆为例）

其中用方框框住的就是整个堆中的最小节点，加粗的节点为打上标记的节点，标记含义为该节点是否已失去一棵子树，我们不允许一个非根节点失去多于一棵子树。

对于插入节点操作，直接加入一个只有根节点的树即可，复杂度显然均摊为 O(1)。

对于减小节点值操作，直接将该节点与其父节点之间的边切断，并标记其父亲已失去一棵子树，然后更新最小节点的指针。（当然，如果操作的节点本身是一个根节点就只需要更新最小节点的指针）若其父节点在此操作之前已失去一棵子树，则需要将其父节点与其父节点的父节点之间的边切断，并不断向上递归，直到遇到一个根节点为止。下面几幅图展示了这个过程：

复杂度分析：每次操作至多给一个新的节点打上标记，至多取出一个未被打标记的节点，而一个被打标记的节点至多只被取出一次，取出一个节点只给整个斐波那契堆增加一个子树，于是复杂度均摊为 O(1)。（取出一个节点的复杂度容易做到 O(1)）

对于删除最小节点操作，将最小节点的所有子树都取出，然后需要保证每个根节点的儿子数互不相同，如果两个根节点的儿子数相同，则需要将值较大的根节点接到值较小的根节点下，使其称为值较小的根节点的子节点。最后更新最小节点的指针即可。下面几幅图展示了这个过程：

复杂度分析：用时显然为第一步结束后树的总数级别。由于删除最小节点操作以及插入节点操作时产生的树的数目已经被均摊到删除最小节点操作和插入节点操作上了，所以本操作的均摊复杂度就是上次合并后的树的数目以及最小值的子节点数的总和，显然与子节点最多的节点的子节点数同阶，我们将说明其为 O(\log n)。

显然我们希望在限制根节点的子节点的最大值为 x 的前提下构造合法的最小的斐波那契堆，记其节点数为 f_x。

为了让节点数最少，显然我们的斐波那契堆肯定只会有一棵树，有 x 个子节点。不难发现有 x 个子节点的堆是由两棵有 x-1 个子节点的堆合并得来的。然后我们让每个节点都尽可能失去一颗子树（除根节点以外），这样节点数最少。于是我们可以在合并后把作为儿子的有 x 个子节点的堆的最大的子树去除即可，那么我们就可以认为一个根有 x 个子节点的堆是由一个根有 x-1 个子节点的堆和一个根有 x-2 个子节点的堆合并而来。前几个堆是这样的：（省略最小节点标记，比较大的节点有标记）

那么我们有：

显然 f_x=F_{x+1}，其中 F_x 为斐波那契数列。（这也是斐波那契堆得名的由来）

众所周知，F_x=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^x-\left(\frac{1-\sqrt{5}}{2}\right)^x}{\sqrt{5}} 是指数级增长的，于是 n 个节点的斐波那契堆的子节点最多的节点的子节点数为 O(\log n) 量级的。

关于斐波那契堆的具体实现还需要注意以下几点：

1. 存储斐波那契堆时每个节点需存储其左儿子（如果存在）、左右兄弟（根节点的左右兄弟也为根节点）和父节点（如果存在）的指针以便快速修改其形态。即一个节点的所有儿子组成一个双向链表，所有根节点也组成一个双向链表。
2. 原则上，根节点不应被标记缺少一颗子树，所以将一个节点取出时记得将其标记清除。
3. 在执行删除最小节点操作时可以准备一个指针数组存储目前子节点数为 i 的子树的根节点，然后扫一遍将所有子树插入其中，一旦出现冲突就合并。记得每次清空。
4. 在其他题目中，如果需要合并两个斐波那契堆，直接将两个根节点链表合并即可，均摊复杂度显然为 O(1)。

普通的斐波那契堆优化 dijkstra 复杂度可以达到 O(n\log n+m) 的最优复杂度，本题复杂度也被顺利优化为 O(n^2\log n+nm)，压位后显然可过。

这是我的 AC 记录。

参考代码如下：（不含注释）

#include<cstdio>
using namespace std;
long long n,m,x[114514],y[114514],z[114514],num[2085],*mp[2085],*mpv[2085],bj[2085],cnt[4096],a,b,i,j,k,dr;
class integer
{
    public:
    long long d[321],r;
    integer():r(0)
    {
        long long i;
        for(i=0;i<321;i++)
        d[i]=0;
    }
    integer & operator = (const integer &x)
    {
        long long i;
        for(i=0;i<251;i++)
        this->d[i]=x.d[i];
        this->r=x.r;
        return *this;
    }
    const integer & operator - (const integer &x) const
    {
        long long i,j=0;
        static integer c;
        for(i=0;i<251;i++)
        c.d[i]=this->d[i]-x.d[i];
        for(i=0;i<251;i++)
        {
            c.d[i]=c.d[i]-j;
            if(c.d[i]<0)
            {
                c.d[i]=c.d[i]+10000000000000000;
                j=1;
            }
            else
            j=0;
        }
        for(i=250;i>0;i--)
        if(c.d[i]>0)
        break;
        c.r=i;
        return c;
    }
    const integer & operator << (long long x) const
    {
        long long i,j=0;
        static integer c;
        for(i=0;i<251;i++)
        c.d[i]=this->d[i]*x;
        for(i=0;i<251;i++)
        {
            c.d[i]=c.d[i]+j;
            j=c.d[i]/10000000000000000;
            c.d[i]=c.d[i]%10000000000000000;
        }
        for(i=250;i>=0;i--)
        {
            c.d[i]=c.d[i]+j*10000000000000000;
            j=c.d[i]%100;
            c.d[i]=c.d[i]/100;
        }
        for(i=250;i>0;i--)
        if(c.d[i]>0)
        break;
        c.r=i;
        return c;
    }
    const integer & operator * (long long x) const
    {
        long long i,j=0;
        static integer c;
        for(i=0;i<251;i++)
        c.d[i]=this->d[i]*x;
        for(i=0;i<251;i++)
        {
            c.d[i]=c.d[i]+j;
            j=c.d[i]/10000000000000000;
            c.d[i]=c.d[i]%10000000000000000;
        }
        for(i=250;i>0;i--)
        if(c.d[i]>0)
        break;
        c.r=i;
        return c;
    }
    bool operator > (const integer &x) const
    {
        long long i;
        if(this->r!=x.r)
        return this->r>x.r;
        for(i=this->r;i>=0;i--)
        if(this->d[i]!=x.d[i])
        return this->d[i]>x.d[i];
        return false;
    }
    bool operator >= (const integer &x) const
    {
        long long i;
        if(this->r!=x.r)
        return this->r>x.r;
        for(i=this->r;i>=0;i--)
        if(this->d[i]!=x.d[i])
        return this->d[i]>x.d[i];
        return true;
    }
}dis[2085],t,w[4096];
const integer ept;
class node
{
    public:
    bool fl;
    node *fa,*ll,*rr,*lson;
    long long snum;
    const integer *wh;
    node():fl(false),fa(NULL),ll(NULL),rr(NULL),lson(NULL),snum(0),wh(NULL){}
}*heap[2085],*top,*c[40];
void out()
{
    long long i;
    node *s,*t,*z;
    while(top->snum>0)
    {
        s=top->lson;
        top->lson=s->rr;
        s->ll=top;
        s->rr=top->rr;
        s->ll->rr=s;
        s->rr->ll=s;
        s->fa=NULL;
        s->fl=false;
        top->snum--;
    }
    top->ll->rr=top->rr;
    top->rr->ll=top->ll;
    s=top->rr;
    delete top;
    if(s==top)
    {
        top=NULL;
        return;
    }
    top=s;
    for(i=0;i<=20;i++)
    c[i]=NULL;
    c[top->snum]=top;
    t=s->rr;
    while(1)
    {
        s=t;
        t=s->rr;
        if(c[s->snum]==s||s->fa!=NULL)
        break;
        if(c[s->snum]==NULL)
        {
            c[s->snum]=s;
            if(*s->wh>*top->wh)
            top=s;
            continue;
        }
        for(j=s->snum;;j++)
        {
            z=c[j];
            if(z==NULL)
            {
                c[j]=s;
                if(*s->wh>=*top->wh)
                top=s;
                break;
            }
            if(*s->wh>*z->wh)
            {
                z=s;
                s=c[j];
            }
            c[j]=NULL;
            z->snum++;
            s->fa=z;
            s->rr->ll=s->ll;
            s->ll->rr=s->rr;
            if(z->snum==1)
            {
                s->ll=s;
                s->rr=s;
            }
            else
            {
                s->rr=z->lson;
                s->ll=s->rr->ll;
                s->rr->ll=s;
                s->ll->rr=s;
            }
            z->lson=s;
            s=z;
        }
    }
}
void update(node *s)
{
    node *p=s->fa;
    if(p==NULL)
    return;
    if(s->fl==false)
    {
        s->fl=true;
        return;
    }
    s->fl=false;
    p->snum--;
    if(p->lson==s)
    if(p->snum==0)
    p->lson=NULL;
    else
    p->lson=s->rr;
    if(p->snum>0)
    {
        s->rr->ll=s->ll;
        s->ll->rr=s->rr;
    }
    s->ll=top;
    s->rr=top->rr;
    s->rr->ll=s;
    s->ll->rr=s;
    s->fa=NULL;
    update(p);
}
void up(int wh)
{
    node *p=heap[wh]->fa;
    if(p==NULL)
    {
        if(*heap[wh]->wh>*top->wh)
        top=heap[wh];
        return;
    }
    heap[wh]->fl=false;
    p->snum--;
    if(p->lson==heap[wh])
    if(p->snum==0)
    p->lson=NULL;
    else
    p->lson=heap[wh]->rr;
    if(p->snum>0)
    {
        heap[wh]->rr->ll=heap[wh]->ll;
        heap[wh]->ll->rr=heap[wh]->rr;
    }
    heap[wh]->ll=top;
    heap[wh]->rr=top->rr;
    heap[wh]->rr->ll=heap[wh];
    heap[wh]->ll->rr=heap[wh];
    heap[wh]->fa=NULL;
    if(*heap[wh]->wh>*top->wh)
    top=heap[wh];
    update(p);
}
main()
{
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
        num[x[i]]++;
        num[y[i]]++;
    }
    for(i=1;i<=n;i++)
    {
        mp[i]=new long long[num[i]+1];
        mpv[i]=new long long[num[i]+1];
        mp[i][0]=0;
    }
    for(i=1;i<=m;i++)
    {
        mp[x[i]][0]++;
        mp[x[i]][mp[x[i]][0]]=y[i];
        mpv[x[i]][mp[x[i]][0]]=z[i];
        mp[y[i]][0]++;
        mp[y[i]][mp[y[i]][0]]=x[i];
        mpv[y[i]][mp[y[i]][0]]=z[i];
    }
    scanf("%lld%lld",&a,&b);
    dis[a].d[250]=1;
    dis[a].r=250;
    for(i=1;i<=n;i++)
    heap[i]=new node;
    for(i=1;i<=n;i++)
    heap[i]->wh=&dis[i];
    for(i=1;i<n;i++)
    heap[i]->rr=heap[i+1];
    heap[n]->rr=heap[1];
    for(i=2;i<=n;i++)
    heap[i]->ll=heap[i-1];
    heap[1]->ll=heap[n];
    top=heap[a];
    for(i=1;i<=n;i++)
    {
        k=top->wh-dis;
        bj[k]=1;
        out();
        for(j=1;j<=mp[k][0];j++)
        if(bj[mp[k][j]]==0)
        {
            t=dis[k]<<100-mpv[k][j];
            if(t>dis[mp[k][j]])
            {
                dis[mp[k][j]]=t;
                up(mp[k][j]);
            }
        }
    }
    t=ept;
    t.d[250]=10000000000;
    t.r=250;
    w[0]=dis[b];
    for(i=1;;i++)
    {
        w[i]=w[i-1]*10;
        if(w[i]>=t)
        break;
    }
    dr=i;
    for(i=dr;i>=0;i--)
    {
        while(t>=w[i])
        {
            t=t-w[i];
            cnt[i]++;
        }
    }
    if(t*2>=w[0])
    cnt[0]++;
    for(i=0;i<=dr;i++)
    if(cnt[i]>9)
    {
        cnt[i]=0;
        cnt[i+1]++;
    }
    for(i=dr;i>8;i--)
    if(cnt[i]>0)
    break;
    for(;i>=0;i--)
    {
        printf("%lld",cnt[i]);
        if(i==8)
        printf(".");
    }
}

后记

好像斐波那契堆没什么人学？而且还有人扬言斐波那契堆在 OI 界没有任何用处。

其实斐波那契堆的常数没有想象中那么大，我感受了一下，感觉常数会比 splay 稍小。

代码也没有想象中那么难写，这题我的代码里斐波那契堆只占了不到 2.2\text{K}，高精度占了超过 1.8\text{K}，可见斐波那契堆和高精度代码难度相当。

这题的高精度恰恰导致了链表操作几乎不占时间，所以这题斐波那契堆的表现其实挺不错的。

最新消息

管理员刚刚说“保证答案不超过 10^4”，所以以上 hack 均不成立。

详情见工单页面。