洛谷 P2387 [NOI2014] 魔法森林 题解【动态加点 SPFA】

题目大意

给定一个由 \(n\) 个点 \(m\) 条边的无向图，每条边有权值 \((a,b)\)，求一条路径使这条路径上的 \((a_{\max}+b_{\max})\) 最小。

思路

正解应该是 LCT 动态维护 MST，本篇题解介绍一种“歪解”——动态加点 SPFA。

我们先只考虑一个权值，那么这就是最单纯的最短路，跑一遍 SPFA 即可。

考虑有两个权值，我们可以从小到大枚举 \(a\)，每次加边之后对 \(b\) 跑一遍 SPFA，若答案被更新，那么贡献一定是新加的 \(a\) 产生的。

由于我们不断加边，如果新加的边对答案有影响，那么 SPFA 时必然经过了这条边的两个端点。因此我们使用动态加点 SPFA，每次新加一条边之后将这条边的两个端点放入队列，然后更新全图的答案。

优化

• 为保证单调性以及时间复杂度，我们不对 \(dis\) 数组更新。
• 把 \(a\) 排序后枚举，随 \(a\) 权值递增而加边。

代码

//P2387 [NOI2014] 魔法森林
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAXN=5e4+10,MAXM=1e5+10,INF=0x3f3f3f3f;
struct Node
{
    int to,a,b;
};
struct Edge
{
    int from,to,a,b;
    bool operator <(Edge y)const
    {
        return a<y.a;
    }
}e[MAXM];
int n,m,dis[MAXN],ans=INF;
bool vis[MAXN];
queue<int> q;
vector<Node> g[MAXN];
void SPFA(int a)
{
    int u;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        vis[u]=false;
        for(Node v:g[u])
        {
            if(max(dis[u],v.b)<dis[v.to])
            {
                dis[v.to]=max(dis[u],v.b);
                if(!vis[v.to])
                {
                    q.push(v.to);
                    vis[v.to]=true;
                }
            }
        }
    }
    ans=min(ans,dis[n]+a);
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&e[i].from,&e[i].to,&e[i].a,&e[i].b);
    }
    sort(&e[1],&e[m+1]);
    fill(&dis[2],&dis[n+1],INF);
    for(int i=1,j;i<=m;i=j)
    {
        j=i;
        while(e[j].a==e[i].a)
        {
            g[e[j].from].push_back({e[j].to,e[j].a,e[j].b});
            g[e[j].to].push_back({e[j].from,e[j].a,e[j].b});
            q.push(e[j].from);
            q.push(e[j].to);
            vis[e[j].from]=vis[e[j].to]=true;
            j++;
        }
        SPFA(e[i].a);
    }
    printf("%d\n",(ans==INF?-1:ans));
    return 0;
}
/*
 * 洛谷
 * https://www.luogu.com.cn/problem/P2387
 * C++20 -O0
 * 2022.10.9
 */

附录

1. 一些其他的非必要的优化：对 \(a\) 去重，Dijkstra 实现的堆优化等，参见 https://blog.csdn.net/Vmurder/article/details/39007471。
2. 本题动态加边 LCT 维护 MST 的做法，参见 https://blog.csdn.net/ylsoi/article/details/79863161。