题面 P2685

分析

题目的意思即：已知一个图，现在要从点$1$走到点$n$，求删掉一条边后最短路的最大值，并求出方案数。

对题目进行分析，可知删去的边一定在原最短路径上。

那么就分别以$1,n$为源点跑一次$\text{Dijsktra}$，得到的距离信息分别是$dis1[u],dis2[u]$。

可以这样想：如果有一条边$<u,v>$不在最短路径上，而经过边$<u,v>$的最短路径与原最短路径的离源点最远的重合点分别为$l[u]$和$r[v]$，可以理解为与源点的$\text{LCA}$。这个可以靠$\text{bfs}$解决。则删掉某条边后，最短路径就有可能变成：$$1\rightarrow l[u]\rightarrow u\rightarrow v\rightarrow r[v]\rightarrow n$$ 由于经过边$<u,v>$的最短路径长度是：$$Dis=dis1[u]+l_{<u,v>}+dis2[v]$$ 那么原最短路径上在$l[u],r[v]-1$两点间所有边的删除都可能使新的路径长度变成$Dis$。由于是最短路，所以显然要取最小值。

因此，这个最小值就可以用线段树来维护。 线段树维护的是原最短路径上的边，节点值表示删除区间内的边后最短路的长度。最后可以扫一遍线段树，即可得到答案。

$\text{Dijsktra}$

裸的最短路，复习一下。

void dijsktra(int *dis, int s)
{
    fill(dis, dis + m + 1, INF);
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(make_pair(0, s));
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(vis[u])
            continue;
        vis[u] = true;
        for(int i = last[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(vis[v])
                continue;
            if(dis[u] + edge[i].val < dis[v])
            {
                dis[v] = dis[u] + edge[i].val;
                q.push(make_pair(dis[v], v));
            }
        }
    }
    return;
}

找到原最短路

暴力即可。

void get_path()
{
    int u = 1;
    while(u != n)
    {
        path[++path_tot] = u;
        id[u] = path_tot;
        for(int i = last[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(dis2[u] == dis2[v] + edge[i].val)
            {
                in_path[i] = true;
                u = v;
                break;
            }
        }
    }
    path[++path_tot] = n;
    id[n] = path_tot;
    return;
}

$\text{bfs}$

由于是带边权最短路树上$\text{bfs}$，因此可以使用一定的技巧。比如这里，可以加入记忆化搜索的优化方式。

void bfs(int *dis, int *end_point, int s)
{
    queue <int> q;
    q.push(path[s]);
    end_point[path[s]] = s;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = last[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(!id[v] && !end_point[v] && dis[u] + edge[i].val == dis[v])
            {
                end_point[v] = s;
                q.push(v);
            }
        }
    }
    return;
}

主程序

跑完两遍$\text{Dijsktra}$之后，先找到原路径，然后对于原路径上的每个点进行正反两次$\text{bfs}$，将得到的$\text{LCA}$分别放到$l[u],r[u]$中。此后，枚举每一条不在原路径上的边，对于$l[u]<r[v]$（即有效边）用之前提到的$Dis$计算方法更新线段树，最后一次性$pushdown()$即可得出最后结果。

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int s, t, c;
        scanf("%d %d %d", &s, &t, &c);
        build_edge(s, t, c);
        build_edge(t, s, c);
    }
    dijsktra(dis1, 1);
    dijsktra(dis2, n);
    get_path();
    for(int i = 1; i <= path_tot; i++)
        bfs(dis1, l, i);
    for(int i = path_tot; i >= 1; i--)
        bfs(dis2, r, i);
    tr.init(1, 1, path_tot);
    for(int u = 1; u <= n; u++)
    {
        for(int i = last[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(!in_path[i] && l[u] && r[v] && l[u] < r[v])
                tr.update(1, l[u], r[v] - 1, dis1[u] + edge[i].val + dis2[v]);
        }
    }
    tr.pushdown(1);
    int cnt = 0, ans = 0;
    for(int i = 1; i < path_tot; i++)
    {
        if(res[i] > ans)
        {
            cnt = 1;
            ans = res[i];
        }
        else
        {
            if(res[i] == ans)
                cnt++;
        }
    }
    if(ans == dis1[n])
        cnt = m;
    printf("%d %d", ans, cnt);
    return 0;
}

完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500010;
const int INF = 0x3f3f3f3f;
struct EDGE
{
    int to, next, val;
};
struct TREE
{
    int l, r, val;
};
EDGE edge[MAXN << 1];
bool in_path[MAXN], vis[MAXN];
int last[MAXN];
int n, m;
int res[MAXN], dis1[MAXN], dis2[MAXN];
int path[MAXN], id[MAXN], path_tot = 0;
int l[MAXN], r[MAXN];

class SegTree
{
  private:
    TREE tree[MAXN << 3];
  public:
    void init(int x, int l, int r)
    {
        tree[x].l = l, tree[x].r = r;
        tree[x].val = INF;
        if(l == r)
            return;
        int mid = (l + r) >> 1;
        init(x<<1, l, mid);
        init(x<<1|1, mid + 1, r);
        return;
    }
    void update(int x, int l, int r, int key)
    {
        int ll = tree[x].l, rr = tree[x].r;
        if(l <= ll && rr <= r)
        {
            tree[x].val = min(tree[x].val, key);
            return;
        }
        int mid = (ll + rr) >> 1;
        if(l <= mid)
            update(x<<1, l, r, key);
        if(r > mid)
            update(x<<1|1, l, r, key);
        return;
    }
    void pushdown(int x)
    {
        int l = tree[x].l, r = tree[x].r;
        if(l == r)
        {
            res[l] = tree[x].val;
            return;
        }
        tree[x<<1].val = min(tree[x].val, tree[x<<1].val);
        tree[x<<1|1].val = min(tree[x].val, tree[x<<1|1].val);
        pushdown(x<<1);
        pushdown(x<<1|1);
        return;
    }
};
SegTree tr;

void build_edge(int u, int v, int val)
{
    static int id = 0;
    edge[++id].to = v;
    edge[id].val = val;
    edge[id].next = last[u];
    last[u] = id;
    return;
}

void dijsktra(int *dis, int s)
{
    fill(dis, dis + m + 1, INF);
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(make_pair(0, s));
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(vis[u])
            continue;
        vis[u] = true;
        for(int i = last[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(vis[v])
                continue;
            if(dis[u] + edge[i].val < dis[v])
            {
                dis[v] = dis[u] + edge[i].val;
                q.push(make_pair(dis[v], v));
            }
        }
    }
    return;
}

void get_path()
{
    int u = 1;
    while(u != n)
    {
        path[++path_tot] = u;
        id[u] = path_tot;
        for(int i = last[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(dis2[u] == dis2[v] + edge[i].val)
            {
                in_path[i] = true;
                u = v;
                break;
            }
        }
    }
    path[++path_tot] = n;
    id[n] = path_tot;
    return;
}

void bfs(int *dis, int *end_point, int s)
{
    queue <int> q;
    q.push(path[s]);
    end_point[path[s]] = s;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = last[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(!id[v] && !end_point[v] && dis[u] + edge[i].val == dis[v])
            {
                end_point[v] = s;
                q.push(v);
            }
        }
    }
    return;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int s, t, c;
        scanf("%d %d %d", &s, &t, &c);
        build_edge(s, t, c);
        build_edge(t, s, c);
    }
    dijsktra(dis1, 1);
    dijsktra(dis2, n);
    get_path();
    for(int i = 1; i <= path_tot; i++)
        bfs(dis1, l, i);
    for(int i = path_tot; i >= 1; i--)
        bfs(dis2, r, i);
    tr.init(1, 1, path_tot);
    for(int u = 1; u <= n; u++)
    {
        for(int i = last[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(!in_path[i] && l[u] && r[v] && l[u] < r[v])
                tr.update(1, l[u], r[v] - 1, dis1[u] + edge[i].val + dis2[v]);
        }
    }
    tr.pushdown(1);
    int cnt = 0, ans = 0;
    for(int i = 1; i < path_tot; i++)
    {
        if(res[i] > ans)
        {
            cnt = 1;
            ans = res[i];
        }
        else
        {
            if(res[i] == ans)
                cnt++;
        }
    }
    if(ans == dis1[n])
        cnt = m;
    printf("%d %d", ans, cnt);
    return 0;
}