传送门:[NOI2014]魔法森林

题意:给一张$n$个点$m$条边的无向图,每个边有两个边权$A_i$和$B_i$,求一条从$1$到$n$的$Path$,使得$\forall edge_i \in Path\;Max(A_i)+Max(B_i)$最小,$n\leq 5w,m\leq 10w$

听说这是一道lct模板题,但作为一个数据结构薄弱选手我肯定是不会lct的QAQ

于是我们可以魔改SPFA

解法1:
枚举边权$A_i$的最大值$A_{max}$,将所有$A_i\leq A_{max}$的边全部加进队列,然后将$B_i$作为边权跑SPFA~
复杂度:$\Theta(knm)$

那咋整呀,要算上述所有情况的最短路是不可避免的吧?
——所以我们可以尝试动态加边啦~

解法2:
首先将权值$A$排序,从小到大依次取边,那么我们会发现每次加入的边就那1条,何必再跑一次SPFA呢?但是我们要思考一下如何动态加边,SPFA有一个队列,里面的元素都是有机会对整张图再次进行松弛操作的(从而进一步优化$dis[]$的权值大小),我们不妨在加边的时候判断一下它连接的两个点是否可以通过它进行松弛操作(就这道题而言就是$max(dis[u],e[u][v])<dis[v]$)如果可以进行松弛操作就将它加入队列,然后对这条边跑一边SPFA即可更新全图。

时间复杂度是:$\Theta(kn)$

代码:

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define mod 1000000007
#define ll long long
#define M 210005
#define N 50005
#define inf (1 << 29)
struct IN{
    int x, y, a, b;
    friend inline bool operator < (IN const &x, IN const &y)
    {
        return x.a < y.a;
    }
}in[M >> 1];
struct edge{
    int to, nxt, b;
}e[M];
int n, m, tot, d[N], head[N], ans = inf;
struct node{
    int d, pos;
    friend inline bool operator < (const node &x, const node &y)
    {
        return x.d > y.d;
    }
};
std::priority_queue <node> q;
inline void addedge (int u, int v, int b)
{
    e[++tot] = (edge) {v, head[u], b};
    head[u] = tot;
    e[++tot] = (edge) {u, head[v], b};
    head[v] = tot;
}
inline void spfa ()
{
    while (!q.empty())
    {
        node u = q.top(); q.pop();
        while (u.d != d[u.pos] && !q.empty())
        {
            u = q.top();
            q.pop();
        }
        if (q.empty() && u.d != d[u.pos]) break;
        for (int i = head[u.pos]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            if (std::max(d[u.pos], e[i].b) < d[v])
            {
                d[v] = std::max(d[u.pos], e[i].b);
                q.push((node) {d[v], v});
            }
        }
    }
}
int main ()
{
    scanf("%d %d", &n, &m);
    fo (i, 1, m)
        scanf("%d %d %d %d", &in[i].x, &in[i].y, &in[i].a, &in[i].b);
    std::sort(in + 1, in + m + 1);
    fo (i, 2, n) d[i] = inf;
    fo (i, 1, m)
    {
        addedge(in[i].x, in[i].y, in[i].b);
        int u = in[i].x, v = in[i].y;
        if (d[u] > d[v]) std::swap(u, v);
        if (std::max(d[u], in[i].b) < d[v])
        {
            d[v] = std::max(d[u], in[i].b);
            q.push((node) {d[v], v});
            spfa();
        }
        ans = std::min(ans, d[n] + in[i].a);
    }
    if (ans == inf)
        printf("-1");
    else
        printf("%d", ans);
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *