题解 P1186 【玛丽卡】

· · 题解

题目大意

给定一张 n 个点 m 条边的带权无向图。现在需要删除一条边，使得 1 到 n 的最短路的长度最大，输出这个最大长度。

题解

大多数错误的做法是枚举最短路上的边并删除，然后重新跑一遍最短路。如果用优先队列优化（劣化）的 \text{Dijkstra}，这么做的复杂度是 \mathcal O(nm\log m)；哪怕使用了朴素的 \text{Dijkstra}，复杂度也是 \mathcal O(mn^2)，无法通过在神 \text{\color{red}\textcolor{black}Imakf} 添加的三个 \text{Hack} 数据。

但可以发现，虽然我们不大能快速求出删除了一条边后的 1 到 n 的最短路，但是我们可以考虑，在强行让一条边被走，可以让哪些原先最短路上的边不需要被走。当我们删除了原先最短路上的某条边 e 后，会产生一些替代路径，这么做本质上就是枚举了替代路径上面的边，求出删掉 e 后会产生的最短路。替代路径的长度的最小值，就是删除 e 对答案的贡献。

下文中，设 \mathcal{E} 为原先的最短路。

可以证明，\mathcal{E} 上原来必须要走，后来不需要被走的边必然是连续的一条路径。使用反证法。我们硬点了一条路径 s\to t。考虑 \mathcal{E} 上路径 a\to b\to c\to d，其中 a\to b,c\to d 这两段都是硬点前必须要走，硬点后不需要被走的路径（但是 a,d 这两个点是一直要被经过的），而 b\to c 则是一直要走的路径。如果 a\to b 后来不需要走，那么必然存在一个走法绕过了 a\to b：从 1 走到了 s\to t，再经过了一些边到了 b（必须会到达 b，不然无法保证 b\to c 是必须走的边；同时在 b 之前必然会经过 s\to t，否则就与 a\to b 原来必须要走的假设矛盾了）；同理，存在走法从 c 走到 s\to t 再到终点 n。那么可以发现，存在一种更短的方案不经过 b\to c，与假设矛盾。因此这些被搁置的最短路上的边必然是连续的路径。

下面考虑怎么求出这个连续段的开头和结尾。一种可行的方法是，分别以 1 和 n 作为起点跑单源最短路。对于每个点，分别求出在这两次单源最短路过程中，到达它所经过的最后一个原先在 \mathcal{E} 上的点（不妨分别记为 A_i,B_i）。当我们枚举替代路径上的边 u\to v 时，我们断言 \mathcal{E} 上的 A_u,B_v 中间的边是会被搁置的。为什么这样是正确的呢？首先，硬点后 1\to A_u\to u\to v\to B_v\to n 肯定是现在的最短路。如果我们选择了一部分 \mathcal{E} 上 A_u,B_v 的路径，肯定是不优的。但可能有些不必要被走的边不在 \mathcal{E} 上 A_u,B_v 之间的边里。这样是不会影响到答案的正确性的：假设有一条不在其中的边 e 成了漏网之鱼，那么肯定会有一条路径横跨 e 的两侧；后来我们肯定会枚举到这条路径上的边，然后重新把 e 给标记了。

整理一下我们要做的事情：

关于第二步，考虑使用并查集。因为跑完单源最短路后本质上形成了一棵类似于树一样的东西，每个节点都有一个前驱节点。我们把 \mathcal{E} 上的节点的前驱赋值为它本身，相当于把这个树形结构拆成了一堆树，每棵树的根节点都是 \mathcal{E} 上的节点。使用路径压缩，可以快速求出一个节点所处子树的根节点是什么（也就是到达它的最短路上最后的 \mathcal{E} 上的点的标号）。

关于第 3,4 步，我们可以使用线段树维护。首先把整个最短路按照顺序映射成 1,2,\cdots 那么最短路上的一条路径就转换为了一串连续的数字。我们要做的是区间赋值、单点查询历史最小值。考虑使用类似于标记永久化的方法：每个线段对应的节点存储一个 \text{tag}，当进行区间赋值时，若该线段被完全覆盖，则将 \text{tag} 更新为权值和 \text{tag} 值的最小值；若没完全覆盖，则递归操作。当我们查询时，统计查询的路径上所有节点的 \text{tag} 的最小值。容易证明这种做法的正确性。

虽然证明内容写起来蛮多的，也不大容易理解，但是代码还算好写……总复杂度 \mathcal O(n^2\log n)，可以通过 \text{\color{red}\textcolor{black}Imakf} 的三个 \text{Hack} 数据和原来的数据。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =1e9;
const int MAXN=1e3+3;
namespace Seg{
    const int SIZ=MAXN*4; int T[SIZ];
    #define lc(t) (t<<1)
    #define rc(t) (t<<1|1)
    void bld(int t,int a,int b){
        T[t]=INF; if(a==b) return; int c=a+b>>1;
        bld(lc(t),a,c),bld(rc(t),c+1,b);
    }
    void sst(int t,int a,int b,int l,int r,int w){
        if(l<=a&&b<=r) T[t]=min(T[t],w); else {
            int c=a+b>>1;
            if(l<=c) sst(lc(t),a,c  ,l,r,w);
            if(r> c) sst(rc(t),c+1,b,l,r,w);
        }
    }
    int  qry(int t,int a,int b,int p){
        if(a==b) return T[t]; int c=a+b>>1;
        if(p<=c) return min(T[t],qry(lc(t),a,c  ,p));
        else     return min(T[t],qry(rc(t),c+1,b,p));
    }
}
namespace Slv{
    int n,m,o,ans; bool U[MAXN][MAXN];
    int A[MAXN],B[MAXN],W[MAXN][MAXN]; bool V[MAXN];
    int P[MAXN],Q[MAXN],I[MAXN];
    int qread(){
        int w=1,c,ret;
        while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
        while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
        return ret*w;
    }
    void dij(int s,int t,int *D,int *E){
        up(1,n,i) D[i]=INF,V[i]=false; D[s]=0; up(1,n,i){
            int f=0;
            up(1,n,j) if((!f||D[j]<D[f])&&!V[j]) f=j; V[f]=true;
            up(1,n,j) if(!V[j]&&D[f]+W[f][j]<D[j]) D[j]=D[f]+W[f][j],E[j]=f;
        }
        if(!o){
            for(int p=t;p;p=E[p]) I[p] =--o; o=-o;
            for(int p=t,q=t;p;q=p,p=E[p]) I[p]+=o+1,U[p][q]=true;
        }
        up(1,n,i) if(I[i]) E[i]=i;
    }
    int gtf(int x,int *F){return x==F[x]?x:F[x]=gtf(F[x],F);}
    void slv(){
        n=qread(),m=qread();
        up(1,n,i) up(1,n,j) W[i][j]=INF;
        up(1,m,i){
            int u=qread(),v=qread(),w=qread();
            if(w<W[u][v])   W[u][v]=W[v][u]=w;
        }
        dij(1,n,A,P),dij(n,1,B,Q),Seg::bld(1,1,o);
        up(1,n,i) up(1,n,j) if(!U[i][j]&&!U[j][i]){
            int w=A[i]+W[i][j]+B[j],s=I[gtf(i,P)],t=I[gtf(j,Q)];
            if(s<t) Seg::sst(1,1,o,s,t-1,w);
        }
        up(1,o-1,i) ans=max(ans,Seg::qry(1,1,o,i));
        printf("%d\n",ans);
    }
}
int main(){
    Slv::slv(); return 0;
}