[BZOJ4912/Luogu3783][SDOI2017]天才黑客(Trie树,最短路径,构造)

发布于 25 天前  63 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4912/Luogu3783][SDOI2017]天才黑客(Trie树,最短路径,构造)

Description

SD0062号选手小Q同学为了偷到SDOI7012的试题,利用高超的黑客技术潜入了SDOI出题组的内联网的中央控制系统,然而这个内联网除了配备有中央控制系统,还为内联网中的每条单向网线设定了特殊的通信口令,这里通信口令是一个字符串,不同网线的口令可能不同。这让小Q同学感觉有些棘手,不过这根本难不倒他,很快他就分析出了整个内联网的结构。
内联网中有 nnn 个节点(从 111 到 nnn 标号)和 mmm 条单向网线,中央控制系统在第 111 个节点上,每条网线单向连接内联网中的某两个节点,从 111 号节点出发经过若干条网线总能到达其他任意一个节点。每个节点都可以运行任意的应用程序,应用程序会携带一条通信口令,当且仅当程序的口令与网线的口令相同时,程序才能通过这条网线到达另一端的节点继续运行,并且通过每条网线都需要花费一定的时间。
每个应用程序可以在任意一个节点修改通信口令,修改通信口令花费的时间可以忽略不计,但是为了减小修改量,需要先调用一个子程序来计算当前程序的口令和网线的口令的最长公共前缀(记其长度为 lenlenlen ),由于获取网线的口令的某个字符会比较耗时,调用一次这个子程序需要花费 lenlenlen 个单位时间。
除此之外,小Q同学还在中央控制系统中发现了一个字典,每条网线的口令都是字典中的某个字符串。具体来说,这个字典是一棵 kkk 个节点(从 111 到 kkk 标号)的有根树,其中根是第 111 个节点,每条边上有一个字符,字符串 SSS 在字典中当且仅当存在某个点u使得从根节点出发往下走到u的这条路径上的字符顺次拼接构成 SSS 。
现在小Q同学在 111 号节点同时开启了 n−1n-1n−1 个应用程序,这些应用程序同时运行且互不干扰,每个程序的通信口令都为空,他希望用最短的时间把这些程序分别发送到其他节点上,你需要帮小Q同学分别计算出发送到第 i(=2,3,…,n)i(=2,3,\dots ,n)i(=2,3,…,n) 个节点的程序完成任务的最短时间。

Tag

Trie树,最短路,构造

解决思路

直接在原图上跑最短路不好记录状态。由于我们知道进入一个点时的口令一定是入边的口令,而出一个点的口令则是离开这个点的边的口令,所以我们想到把边转化成点,这样点权就可以直接固定了。
但是直接连边是\(O(m^2)\)的,所以要考虑优化建图。
一种方法就是,对于原图中的点,把它的所有入边和出边统计(也就是新图中的点),找到它们的口令对应的在\(Trie\)树中的节点,然后构建出虚树。由于\(lcp\)有良好的性质,即\(Trie\)上两点代表的字符串的\(lcp\)长度就是这两个点\(lca\)的深度。所以只需把\(Trie\)的每一个点的每一棵子树中的点相互连边。又因为子树的\(dfn\)序表示为一个连续区间,一个区间在线段树上最多拆分成\(log_n\)个区间,所以,再加上一个辅助点的话可以把边优化到\(log\)级别。
但这样建图还是太麻烦了,这里介绍一种不需要虚树和线段树优化建图的方法。[来源:Clairs]
还是考虑每一条边的口令在\(Trie\)树上的对应的点,按照\(dfn\)序排序后,类似后缀数组中的\(height\)有\(lcp(u,v)=min(height[u],height[u+1],...,height[v-1])\),两个点\(u,v\)的\(lcp\)长度应该就是这两个点之间所有的点中最浅的\(lca\)。
所以,现在的问题是如何建图使得能够得到一段边权取\(min\)的最短路呢?可以采用建立前缀虚点和后缀虚点的方法,建立四排点,分别表示入边前缀,入边后缀,出边前缀和出边后缀,然后在对应的前后缀之间连边,边权为\(lca\)的深度。这样以来,边数和点数均优化到\(O(m)\)级别了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=51000*10;
const int maxM=maxN*10;
const int inf=2147483647;

class EDGE
{
public:
    int a,b,c,d;
};

int n,m,K;
int edgecnt,HeadIn[maxN],HeadOut[maxN],Next[maxN],V[maxN];
EDGE E[maxN];
int PreIn[maxN],PreOut[maxN],SufIn[maxN],SufOut[maxN],Queue[maxN];

void Add(int &head,int v);
void Doing(int id);
bool cmp(int a,int b);

namespace TRIE
{
    const int maxBit=15;

    map<int,int> Son[maxN];
    int dfncnt,Dfn[maxN],Fa[maxBit][maxN],Depth[maxN];

    void Add(int u,int v,int w);
    void Do();
    void dfs_dfn(int u);
    int GetLCA(int u,int v);
}

namespace GRAPH
{
    class HeapData
    {
    public:
        int u,dist;
    };

    int NodeW[maxN];
    int nodecnt;
    int edgecnt=0,Head[maxN],Next[maxM],V[maxM],W[maxM],Dist[maxN];
    bool vis[maxN];
    priority_queue<HeapData> H;

    void Add_Edge(int u,int v,int w);
    bool operator < (HeapData A,HeapData B);
    void Dij();
}

int main()
{
    mem(HeadIn,-1);mem(HeadOut,-1);edgecnt=0;TRIE::dfncnt=0;GRAPH::nodecnt=0;GRAPH::edgecnt=0;mem(GRAPH::Head,-1);
    int TTT;scanf("%d",&TTT);
    while (TTT--)
    {
        scanf("%d%d%d",&n,&m,&K);
        GRAPH::nodecnt=m;
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&E[i].a,&E[i].b,&E[i].c,&E[i].d);
            Add(HeadIn[E[i].b],i);Add(HeadOut[E[i].a],i);
            GRAPH::NodeW[i]=E[i].c;
        }
        for (int i=1;i<K;i++)
        {
            int u,v,w;scanf("%d%d%d",&u,&v,&w);
            TRIE::Add(u,v,w);
        }

        TRIE::Do();

        for (int i=1;i<=n;i++) Doing(i);

        GRAPH::Dij();

        for (int i=2;i<=n;i++)
        {
            int ans=inf;
            for (int j=HeadIn[i];j!=-1;j=Next[j])
                ans=min(ans,GRAPH::Dist[V[j]]);
            printf("%d\n",ans);
        }

        mem(HeadIn,-1);mem(HeadOut,-1);edgecnt=0;TRIE::dfncnt=0;GRAPH::nodecnt=0;GRAPH::edgecnt=0;mem(GRAPH::Head,-1);mem(TRIE::Fa,0);mem(TRIE::Depth,0);mem(GRAPH::NodeW,0);
        for (int i=1;i<=K;i++) TRIE::Son[i].clear();
    }
    return 0;
}

void Add(int &head,int v)
{
    edgecnt++;Next[edgecnt]=head;head=edgecnt;V[edgecnt]=v;
    return;
}

void Doing(int id)
{
    int cnt=0;
    for (int i=HeadIn[id];i!=-1;i=Next[i]) Queue[++cnt]=V[i];
    for (int i=HeadOut[id];i!=-1;i=Next[i]) Queue[++cnt]=-V[i];
    sort(&Queue[1],&Queue[cnt+1],cmp);

    for (int i=1;i<=cnt;i++)
    {
        PreIn[i]=++GRAPH::nodecnt;PreOut[i]=++GRAPH::nodecnt;SufIn[i]=++GRAPH::nodecnt;SufOut[i]=++GRAPH::nodecnt;
        if (i>1)
        {
            GRAPH::Add_Edge(PreIn[i-1],PreIn[i],0);
            GRAPH::Add_Edge(PreOut[i-1],PreOut[i],0);
            GRAPH::Add_Edge(SufIn[i],SufIn[i-1],0);
            GRAPH::Add_Edge(SufOut[i],SufOut[i-1],0);
        }
        if (Queue[i]>0) GRAPH::Add_Edge(Queue[i],PreIn[i],0),GRAPH::Add_Edge(Queue[i],SufIn[i],0);
        if (Queue[i]<0) Queue[i]*=-1,GRAPH::Add_Edge(PreOut[i],Queue[i],0),GRAPH::Add_Edge(SufOut[i],Queue[i],0);
    }

    for (int i=1;i<cnt;i++)
    {
        int lca=TRIE::GetLCA(E[Queue[i]].d,E[Queue[i+1]].d);
        int d=TRIE::Depth[lca]-1;
        GRAPH::Add_Edge(PreIn[i],PreOut[i+1],d);
        GRAPH::Add_Edge(SufIn[i+1],SufOut[i],d);
    }
    return;
}

bool cmp(int u,int v){
    return TRIE::Dfn[E[abs(u)].d]<TRIE::Dfn[E[abs(v)].d];
}

namespace TRIE
{
    void Add(int u,int v,int w){
        Son[u][w]=v;return;
    }

    void Do()
    {
        Depth[1]=1;
        dfs_dfn(1);
        for (int i=1;i<maxBit;i++)
            for (int j=1;j<=K;j++)
                if ((Fa[i-1][j])&&(Fa[i-1][Fa[i-1][j]]))
                    Fa[i][j]=Fa[i-1][Fa[i-1][j]];
        return;
    }

    void dfs_dfn(int u)
    {
        Dfn[u]=++dfncnt;
        for (map<int,int>::iterator i=Son[u].begin();i!=Son[u].end();i++) Depth[(*i).second]=Depth[u]+1,Fa[0][(*i).second]=u,dfs_dfn((*i).second);
        return;
    }

    int GetLCA(int u,int v)
    {
        if (Depth[u]<Depth[v]) swap(u,v);
        for (int i=maxBit-1;i>=0;i--) if ((Fa[i][u])&&(Depth[Fa[i][u]]>=Depth[v])) u=Fa[i][u];
        if (u==v) return u;
        for (int i=maxBit-1;i>=0;i--) if ((Fa[i][u])&&(Fa[i][v])&&(Fa[i][u]!=Fa[i][v])) u=Fa[i][u],v=Fa[i][v];
        return Fa[0][u];
    }
}

namespace GRAPH
{
    void Add_Edge(int u,int v,int w){
        edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=w;return;
    }

    bool operator < (HeapData A,HeapData B){
        return A.dist>B.dist;
    }

    void Dij()
    {
        mem(Dist,127);mem(vis,0);while (!H.empty()) H.pop();
        for (int i=1;i<=m;i++) if (E[i].a==1) if (Dist[i]>NodeW[i]) Dist[i]=NodeW[i],H.push((HeapData){i,Dist[i]});
        do
        {
            int u=H.top().u;H.pop();
            if (vis[u]) continue;
            vis[u]=1;
            for (int i=Head[u];i!=-1;i=Next[i])
                if ((vis[V[i]]==0)&&(Dist[V[i]]>Dist[u]+NodeW[V[i]]+W[i]))
                    Dist[V[i]]=Dist[u]+NodeW[V[i]]+W[i],H.push((HeapData){V[i],Dist[V[i]]});
        }
        while (!H.empty());
        return;
    }
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4912/Luogu3783][SDOI2017]天才黑客(Trie树,最短路径,构造)


HNCJ OIer 一枚