Yuhang's Blog

桥(洛谷P2685)题解

2024-11-17 CodingMathematics

给定一张无向图, 有边权, 可能有重边和自环. 我们用$p_0$表示原图上从节点$1$到$n$的一条最短路. 对图上的任意一条边$e$, 设$p(e)$是删去边$e$后的从$1$到$n$的最短路, 设$f(e)$是$p(e)$的长度. 求$\max_e f(e)$, 并求有多少边$e$能取到这个最大值.

首先观察到, 若$e$不在$p_0$上, 那么$f(e)$显然是$p_0$的长度. 因此只需考虑$e$在$p_0$上的情况.

一个引理: 如果路径$p$是从$u$到$v$的最短路, 而路径$q$是路径$p$的一部分, 并且路径$q$是从$s$到$t$的, 那么$q$是从$s$到$t$的最短路.

反证法: 如果不是, 那么把$p$中的相应部分改成从$s$到$t$的最短路, 那么$p$的长度变小了, 这和$p$是从$u$到$v$的最短路相矛盾.

考虑边$e$. 设$q(e)$是必须经过$e$的从$1$到$n$的最短路. 显然如果$e$在$p_0$上, 那么$q(e)$就是$p_0$. 所以我们考虑$e$不在$p_0$上的情况. 首先如果$e: u \rightarrow v$, 那么$q(e)$无非就是”从$1$到$u$的最短路”加上$e$再加上”从$v$到$n$的最短路”.

我们还有: $q(e)$和$p_0$只有一段连续的部分不重合. 这是因为: 首先$q(e)$一定至少有一部分和$p_0$不重合, 并且这部分包括了$e$, 这是因为$e$不在$p_0$上却在$q(e)$上. 然而, 在这部分之外, 因为$q(e)$和$p_0$都希望最小化路径长度, 利用前面的引理(及其证明思路), 不难发现$q(e)$和$p_0$应该重合.

现在设边$e: u \rightarrow v$不在$p_0$上. 根据上面的讨论, $q(e)$一定符合如下形式: $1 \rightsquigarrow l(u) \rightsquigarrow u \rightarrow v \rightsquigarrow r(v) \rightsquigarrow n$, 其中$l(u)$是$p_0$和从$1$到$u$的最短路的最后一个公共节点, 而$r(v)$是$p_0$和从$v$到$n$的最短路的第一个公共节点.

我们有命题$(\star)$: 如果删去了$p_0$上的某条边$e_1$, 那么新的最短路$p(e_1)$一定等于某个$q(e_2)$, 其中边$e_2: u \rightarrow v$不属于$p_0$. (严格证明见文末.)

进一步, 对于任意的不属于$p_0$的$e_2: u \rightarrow v$, 那么$q(e_2)$等于$p(e_1)$, 只可能是当$e_1$是在$p_0$的$l(u) \rightsquigarrow r(v)$ 这个部分中时. 因为$p(e_1)$中必然不包含$e_1$, 而如果$q(e_2)$也不包含$e_1$, 那么$e_1$一定不在$1 \rightsquigarrow l(u)$和$r(v) \rightsquigarrow n$ 这两个部分之中. 但是$e_1$又在$p_0$之中, 所以只能在$l(u) \rightsquigarrow r(v)$这个部分中.

总结一下. 对于每个$e_1 \in p_0$, 我们想找$p(e_1)$, 而$p(e_1)$是某个最短的$q(e_2)$, 其中$e_2: u \rightarrow v$不属于$p_0$, 并且$e_1$包含在$p_0$的$l(u) \rightsquigarrow r(v)$ 部分中.

因此, 我们可以枚举所有的$e_2 \not \in p_0$, 然后用$q(e_2)$的长度来更新$p_0$的$l(u) \rightsquigarrow r(v)$ 部分中所有边的$f$值. 这就成了区间更新问题, 可以用线段树解决. 这样一来, 枚举结束后, 我们就得到了对于任意$e_1 \in p_0$的所有$f(e_1)$的值. 最终, 只用取所有$f$的最大值即可.

另一种不用线段树的做法是利用multiset和类似于差分的思想. 我们$p_0$上的每个点处维护两个数组add和rmv. 对于每个$q(e_2)$的长度, 它能作为$l(u) \rightsquigarrow r(v)$ 部分中边的$f$值的候选项, 那么我们把$q(e_2)$的长度加入add[l[u]]和rmv[r[v]]之中. 之后, 我们只需从左向右依次扫描$p_0$上的每个边, 并按add和rmv的记录来维护一个表示当前所有候选项的multiset(称为candidates), 每次取candidates中的最小值即可.

还有一个小问题是$l(u)$和$r(v)$怎么求. 我们以$l(u)$为例. 首先如果$u$在$p_0$上, 那么$l(u) = u$. 否则的话, 我们在(从$1$开始的)单源最短路的时候提前记录$u$的前驱$p(u)$, 那么$l(u) = l(p(u))$.

最后, 注意特殊情况是如果所有的$f(e)$都和$p_0$一样长, 那么答案显然是$p_0$的长度, 并且不管删图上的哪个边都能得到这个答案, 所以方案数是边数$m$.

现在我们来证明命题$(\star)$: 对于任意$p_0$上的边$e_1$, 一定存在$e_2 \not \in p_0$, 使得$q(e_2) = p(e_1)$. (严格来说, $q(e_2)$和$p(e_1)$都可能是不唯一的, 因而分别应是一些最短路的集合, 我们这里表示这两个集合有交集.)

考虑以$1$为根的最短路树$T_1$ (它是原图的一个生成树), 这树上每个节点的父节点是最短路算法给出的前驱. $p_0$显然在树$T_1$上. 如果删去边$e_1$, 那么树$T_1$将分裂成两个, 记为$T_2$和$T_3$, 其中节点$1$在树$T_2$上, 而节点$n$在树$T_3$上.

我们可以忽略$T_3$上的连边, 把$T_3$上的节点以$n$为根的最短路树重新连接, 记为$T_3’$. (从而$T_3’$是以$n$为根的最短路树的子树, 且节点集合与$T_3$相同.)

下面, 寻找一条从$1$到$n$的最短路, 就等价于找一条边$e_2: u \rightarrow v$把$T_2$和$T_3’$连起来, 其中$u \in T_2$且$v \in T_3’$, 并且$\text{dist}(1, u) + \text{weight}(e_2) + \text{dist}(v, n)$最小. 这是因为在$T_2$和$T_3’$内部的路径都是最优的, 而连接$T_2$和$T_3’$这两棵树又是必须的. 注意到$e_2$一定不在$p_0$上, 因为$p_0$上的除了$e_1$外的所有边都必定在$T_2$内部或者$T_3’$内部, 而$e_1$已经被删去.

这样我们就构造出了$p(e_1)$. 但上述路径显然等价于$q(e_2)$. 证毕.

使用multiset的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100000 + 123;
const int M = 400000 + 223;
#define rep(i,from,to) for(int i=(int)(from);i<=(int)(to);++i)
struct MyIn { 
    template <typename T> MyIn& operator>> (T &x) { x=0;bool s=0;char c=getchar();while(c>'9'||c<'0'){if(c=='-')s=1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}if(s)x=-x;return (*this); } 
} rin;

#ifdef D
    void dbg() {cerr << "\n";}
    template<typename T, typename... A> void dbg(T a, A... x) {cerr << a << ' '; dbg(x...);}
    #define logs(x...) {cerr << #x << " -> "; dbg(x);}
#else
    #define logs(...) {}
#endif

// tail, weight, index
vector<tuple<int, int, int>> g[N];
// head, tail, weight
vector<tuple<int, int, int>> edges;
int n, m;

ll dist1[N];
ll distn[N];
int pre1[N];
int pren[N];
bool vis[N];
priority_queue<pair<ll, ll>> que;
void dijkstra(int src, ll dist[], int pre[]) {
    memset(dist, 0x3f, sizeof(ll) * N);
    memset(vis, 0, sizeof(vis));
    dist[src] = 0;
    que.push(make_pair(0, src));
    while (que.size()) {
        auto [d, u] = que.top();
        que.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto &[v, w, i]: g[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                que.push(make_pair(-dist[v], v));
                // record the index of edge
                pre[v] = i;
            }
        }
    }
}

int on_shortest[N]; // if a vertex is on the shortest path, then its index. o/w 0
bool edge_on_shortest[M];  // whether an edge is on the shortest path
int shortest_cnt; // number of vertices on the shortest path = # of edges + 1
void find_shortest() {
    int i = 1;
    shortest_cnt = 1;
    while (i != n) {
        on_shortest[i] = shortest_cnt;
        shortest_cnt++;
        edge_on_shortest[pren[i]] = 1;
        edge_on_shortest[pren[i] ^ 1] = 1;
        auto [u, v, w] = edges[pren[i]];
        i = u;
    }
    on_shortest[n] = shortest_cnt;
    // vertex index: 1, 2, ..., shortest_cnt
    // edge index: 1, 2, ...., shortest_cnt - 1
    // [1] -(1)-> [2] -(2)-> [3] -> ... -> [cnt-1] -(cnt-1)-> [cnt]
    // ~~cochain complex!!!!~~ (no)
}

int l[N];
int r[N];
void find_lr(int u, int lr[], int pre[]) {
    // find l or r. lr[] is l or r. pre is pre1 or pren.
    if (lr[u]) return;
    if (on_shortest[u]) lr[u] = u;
    else {
        auto [v, _, w] = edges[pre[u]];
        find_lr(v, lr, pre);
        lr[u] = lr[v];
    }
}

vector<ll> add[N];
vector<ll> rmv[N];
multiset<ll> candidates;
void solve() {
    for (int i = 0; i < edges.size(); i++) {
        // enumerate all edges not on the shortest path
        if (edge_on_shortest[i]) continue;
        auto [u, v, w] = edges[i];
        int l_index = on_shortest[l[u]];
        int r_index = on_shortest[r[v]];
        if (l_index >= r_index) continue;
        ll dist = dist1[u] + w + distn[v];
        add[l_index].push_back(dist);
        rmv[r_index].push_back(dist);
    }
    ll ans = 0; int cnt = 0;
    rep(i, 1, shortest_cnt - 1) {
        for (ll u : add[i]) {
            candidates.insert(u);
        }
        for (ll u : rmv[i]) {
            candidates.erase(candidates.find(u));
        }
        if (candidates.size()) {
            ll cur_f = *candidates.begin();
            if (cur_f > ans) {
                ans = cur_f; cnt = 1;
            } else if (cur_f == ans) {
                cnt++;
            }
        }
    }

    if (ans == dist1[n]) cnt = m;

    cout << ans << " " << cnt << endl;
}


int main() {
    #ifdef D
    freopen("in", "r", stdin);
    #endif
    rin >> n >> m;
    rep(i, 1, m) {
        int s, t, c;
        rin >> s >> t >> c;
        g[s].push_back(make_tuple(t, c, edges.size()));
        edges.push_back(make_tuple(s, t, c));
        g[t].push_back(make_tuple(s, c, edges.size()));
        edges.push_back(make_tuple(t, s, c));
        // `edges` have both directions
    }

    dijkstra(1, dist1, pre1);
    dijkstra(n, distn, pren);

    find_shortest();

    rep(i, 1, n) {
        find_lr(i, l, pre1);
        find_lr(i, r, pren);
    }

    solve();
    
}
This article was last updated on days ago, and the information described in the article may have changed.

Published at  , Updated at 

Coding Mathematics