P3783 [SDOI2017]天才黑客 题解

· · 题解

先扯点题外话。最短路有一个性质是说，两个点之间连很多条边等价于连最短的那条边，或者说最短路会自动给重边取\min。

如果我们建图的时候应该连边a\stackrel{w}{\longrightarrow}b，实际上只要保证有一条a\stackrel{w}{\longrightarrow}b，并且其它所有a\stackrel{w^\prime}{\longrightarrow}b都满足w^\prime\geq w即可。当然这个箭头记号表示一条有向边的起点、终点和边权(好像并不标准?但是很形象)。

看到这个题，首先我们有一个显然的结论，那就是lcp就是lca深度(根深度为0)。

考虑对每条边做一个拆点，我们把一条边权为w的边i中间加上一个入点一个出点，记为in_i,out_i，并连边in_i\stackrel{w}{\longrightarrow}out_i。

然后考虑原图中的点仅仅表示边的连通性，所以一个暴力的想法就是去掉原图中的点，而对每个点把它周围所有的边都连一连。具体地，对于每条连向点u的边，把它的出点向每条从u发出的边的入点连边，边权是lca深度。

如果遇到一个点周围有很多边，我们得到的边数就是O(n^2)，会爆炸。

因为最短路是对重边取\min，我们可以考虑能不能把lca深度也搞成一个\min的形式(核心思想)，这样就可以利用最短路的取\min来处理lca深度了。

容易想到使用dfs序lca。dfs序lca的结论是，如果我们记录一棵树的欧拉序(每经过一次都记录一次)，那么两个点的lca就是它们第一次被访问的位置之间深度最小的点。

所以如果我们设d_i表示dfn中第i个位置上那个点的深度，id_u表示点u第一次被访问的时间，那么就有

\mathrm{dep}(\mathrm{lca}(u,v))=\min_{i=id_u}^{id_v}d_i

然后呢?考虑一个d_i什么时候会参与这个取\min的过程，应该是查询的两个点，一个点在它前面，一个点在它后面的时候。

换句话说，这个点的贡献就相当于给它对应的前缀连到后缀，后缀连到前缀，边权是它的深度。!!!我们已经得到做法了!

这里可以使用线段树优化建图，不过更好的方法是使用前后缀和优化建图。

前后缀和优化建图是什么?以前缀和为例，我们新建一排点表示前缀和，前缀和那一排中的点i连向点i-1和原序列中的第i个点，这样它实际上连到了原序列中的前i个点。我们可以使用这个结构支持一个点向一个前缀连边。前缀向点连边，点向后缀连边，后缀向点连边是同样的。

对于这个题，我们需要建四排点，分别表示前缀入点，前缀出点，后缀入点，后缀出点。

这里需要建立虚树，在虚树上求欧拉序，这一步没有难写到一定程度，但是实际上还可以简化，具体可以见别的题解。反正我没想着简化（

复杂度是O((n+m)\log n)。

代码确实很难写!需要一定的封装技巧才能让代码可读，这里我考虑了好久，写了200+lines，还是不可读......

这题还有一些别的做法。网上说的带\log甚至\log^2的树剖和树上倍增做法我实在是没想明白，希望神仙们可以教教我/se

温馨提示 : 多测不清空，爆零两行泪!

code:

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
using std::priority_queue;
using std::sort;
using std::vector;

inline void swap(int &x,int &y){ x^=y^=x^=y; }
inline long long min(long long x,long long y){ return x<y?x:y; }

namespace Tree
{

struct Graph
{
    struct Edge
    {
        int v,next;
    }e[100002];
    int ecnt,h[20002];
    inline void add_edge(int u,int v)
    {
        e[++ecnt]={v,h[u]};
        h[u]=ecnt;
        e[++ecnt]={u,h[v]};
        h[v]=ecnt;
    }
    inline void clear()
    {
        ecnt=0;
        memset(h,0,sizeof(h));
    }
}G,T;

int f[20][40002],id[20002],cnt,dep[20002],lg[40002];

inline void cleartree()
{
    G.clear(),T.clear();
    cnt=0;
}

void predfs(int u,int _fa)
{
    f[0][++cnt]=u,id[u]=cnt;
    dep[u]=dep[_fa]+1;
    for(int i=G.h[u];i;i=G.e[i].next)
        if(G.e[i].v!=_fa)
            predfs(G.e[i].v,u),f[0][++cnt]=u;
}

inline void st_init()
{
    for(int k=1;k<=20;k++)
        for(int i=1;i<=cnt-(1<<k)+1;i++)
            f[k][i]=(dep[f[k-1][i]]<dep[f[k-1][i+(1<<(k-1))]]?f[k-1][i]:f[k-1][i+(1<<(k-1))]);
    for(int i=2;i<=cnt;i++)
        lg[i]=lg[i>>1]+1;
}

inline int lca(int u,int v)
{
    u=id[u],v=id[v];
    if(u>v) swap(u,v);
    int l=lg[v-u+1];
    return dep[f[l][u]]<dep[f[l][v-(1<<l)+1]]?f[l][u]:f[l][v-(1<<l)+1];
}

int s[20002],top;
inline void clear(int u){ T.h[u]=0; }
inline void insert(int u)
{
    int l=lca(u,s[top]);
    if(l!=s[top])
    {
        while(id[l]<id[s[top-1]]) T.add_edge(s[top-1],s[top]),top--;
        if(id[l]!=id[s[top-1]]) clear(l),T.add_edge(l,s[top]),s[top]=l;
        else T.add_edge(l,s[top]),top--;
    }
    clear(u),s[++top]=u;
}

inline bool cmp(int u,int v){ return id[u]<id[v]; }
inline void build(int n,int *a)
{
    sort(a+1,a+n+1,cmp);
    T.ecnt=0,clear(1),s[top=1]=1;
    for(int i=1;i<=n;i++)
        if(a[i]!=1&&a[i]!=a[i-1]) insert(a[i]);
    for(int i=1;i<top;i++) T.add_edge(s[i],s[i+1]);
}

inline void get_dfn(int u,int _fa,int *dfn,int *id,int &cnt)
{
    dfn[++cnt]=dep[u],id[u]=cnt;
    for(int i=T.h[u];i;i=T.e[i].next)
        if(T.e[i].v!=_fa)
            get_dfn(T.e[i].v,u,dfn,id,cnt),dfn[++cnt]=dep[u];
}

}

int ncnt;
inline int new_node(){ return ++ncnt; }

int n,m,k;
int nodein[50002],nodeout[50002],prein[40002],sufin[40002],preout[40002],sufout[40002];
struct Pair{ int u,id; };
vector<Pair> in[50002],out[50002];

namespace Dij
{

struct Edge
{
    int v,w,next;
}e[20000002];

int ecnt,h[2000002];
inline void add_edge(int u,int v,int w)
{
    e[++ecnt]={v,w,h[u]};
    h[u]=ecnt;
}

inline void clear()
{
    ecnt=0;
    memset(h,0,sizeof(h));
}

struct DijNode
{
    int u;long long dis;
};
inline bool operator < (DijNode x,DijNode y){ return x.dis>y.dis; }

long long dis[2000002];
bool vis[2000002];

inline void Dij()
{
    priority_queue<DijNode> q;
    //while(!q.empty()) q.pop();
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<out[1].size();i++)
        dis[out[1][i].u]=0,q.push({out[1][i].u,0});
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=h[u];i;i=e[i].next)
            if(dis[u]+e[i].w<dis[e[i].v])
                dis[e[i].v]=dis[u]+e[i].w,q.push({e[i].v,dis[e[i].v]});
    }
}

}

using Dij::add_edge;

inline void build_graph()
{
    static int temp[100002],dfn[40002],id[100002];
    for(int u=1;u<=n;u++)
    {
        int tcnt=0;
        for(int i=0;i<in[u].size();i++)
            temp[++tcnt]=in[u][i].id;
        for(int i=0;i<out[u].size();i++)
            temp[++tcnt]=out[u][i].id;
        Tree::build(tcnt,temp);
        int cnt=0;
        Tree::get_dfn(1,0,dfn,id,cnt);
        for(int i=1;i<=cnt;i++)
            prein[i]=new_node(),sufin[i]=new_node(),preout[i]=new_node(),sufout[i]=new_node();
        for(int i=2;i<=cnt;i++)
            add_edge(prein[i],prein[i-1],0),
            add_edge(preout[i-1],preout[i],0);
        for(int i=1;i<=cnt-1;i++)
            add_edge(sufin[i],sufin[i+1],0),
            add_edge(sufout[i+1],sufout[i],0);
        for(int i=0;i<in[u].size();i++)
            add_edge(in[u][i].u,preout[id[in[u][i].id]],0),
            add_edge(in[u][i].u,sufout[id[in[u][i].id]],0);
        for(int i=0;i<out[u].size();i++)
            add_edge(prein[id[out[u][i].id]],out[u][i].u,0),
            add_edge(sufin[id[out[u][i].id]],out[u][i].u,0);
        for(int i=1;i<=cnt;i++)
            add_edge(preout[i],sufin[i],dfn[i]),add_edge(sufout[i],prein[i],dfn[i]);
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1,u,v,w,id;i<=m;i++)
            scanf("%d%d%d%d",&u,&v,&w,&id),
            nodein[i]=new_node(),nodeout[i]=new_node(),add_edge(nodein[i],nodeout[i],w),
            in[v].push_back({nodeout[i],id}),out[u].push_back({nodein[i],id});
        for(int i=1,u,v,w;i<k;i++)
            scanf("%d%d%d",&u,&v,&w),Tree::G.add_edge(u,v);
        Tree::dep[0]=-1,Tree::predfs(1,0),Tree::st_init();
        build_graph();
        Dij::Dij();
        for(int i=2;i<=n;i++)
        {
            long long ans=0x7fffffffffffffff;
            for(int j=0;j<in[i].size();j++)
                ans=min(ans,Dij::dis[in[i][j].u]);
            printf("%lld\n",ans);
        }
        Dij::clear();
        Tree::cleartree();
        ncnt=0;
        for(int i=1;i<=n;i++)
            in[i].clear(),out[i].clear();
    }
    return 0;
}