【SDOI2017】天才黑客

梦里梦外; 2021-12-20 10:13 183阅读 0赞

## 【SDOI2017】天才黑客 ##

![img][]  
![img][img 1]  
![img][img 2]  
![img][img 3]

这题太神了。

先模[Claris 大神的题解][Claris]。

首先我们要将边转换为点。如果暴力连边就会有\\(m^2\\)的边，于是我们考虑优化建图。

难点在于快速得到两个边的串的\\(lcp\\)，也就是\\(trie\\)树上的\\(lca\\)。我们将一堆点按\\(dfs\\)序排序，然后\\(a\\)到\\(b\\)的\\(lca\\)就是排序后\\(min\\\{lca(a,a+1),lca(a+1,a+2)...lca(b-1,b)\\\}\\)，这里的\\(min\\)是深度最小。

对于原图上的点\\(i\\)，我们就将所有的边按\\(dfs\\)序拍好序，再复制一倍的虚点，相邻的实点和虚点连权值为\\(0\\)的边。每个实点向下一个点对应的虚点连权值为\\(dep\_\{lca\}\\)的边。

然后还要反方向建相同的边，不过不能建在一张图上。

这道题中关于处理一堆点两两之间\\(lca\\)的方法值得掌握。

代码：

#include<bits/stdc++.h>
    #define ll long long
    #define N 400005
    
    using namespace std;
    inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
    
    int n,m,k;
    int tot,TOT;
    int w[N],t[N];
    ll dis[N];
    ll ans[N];
    vector<int>st[N];
    vector<int>e[N];
    struct road {
        int to,next;
        ll c;
    }s[N*15];
    int h[N],cnt;
    void add(int i,int j,int c) {s[++cnt]=(road) {j,h[i],c};h[i]=cnt;}
    
    int id,dfn[N];
    void Init() {
        cnt=0;
        id=0;
        memset(h,0,sizeof(h));
        memset(t,0,sizeof(t));
        memset(w,0,sizeof(w));
        memset(dis,0x3f,sizeof(dis));
        for(int i=1;i<=k;i++) e[i].clear();
        for(int i=1;i<=n;i++) st[i].clear();
    }
    
    int dep[N];
    int fa[N][20];
    
    bool cmp(int a,int b) {return dfn[t[a]]<dfn[t[b]];}
    bool cmp2(int a,int b) {return dfn[t[a]]>dfn[t[b]];}
    
    int lca(int a,int b) {
        if(dep[a]<dep[b]) swap(a,b);
        for(int i=16;i>=0;i--)
            if(fa[a][i]&&dep[fa[a][i]]>=dep[b])
                a=fa[a][i];
        if(a==b) return a;
        for(int i=16;i>=0;i--)
            if(fa[a][i]!=fa[b][i])
                a=fa[a][i],b=fa[b][i];
        return fa[a][0];
    }
    
    void dfs(int v) {
        dfn[v]=++id;
        for(int i=1;i<=16;i++) fa[v][i]=fa[fa[v][i-1]][i-1];
        for(int i=0;i<e[v].size();i++) {
            int to=e[v][i];
            dep[to]=dep[v]+1;
            fa[to][0]=v;
            dfs(to);
        }
    }
    
    void build() {
        for(int i=1;i<=n;i++) {
            sort(st[i].begin(),st[i].end(),cmp);
            for(int j=0;j<st[i].size()-1;j++) {
                add(st[i][j],st[i][j+1],0);
                add(st[i][j]+tot,st[i][j+1]+tot,0);
                add(st[i][j],st[i][j+1]+tot,dep[lca(t[st[i][j]],t[st[i][j+1]])]);
            }
            reverse(st[i].begin(),st[i].end());
            for(int j=0;j<st[i].size()-1;j++) {
                add(st[i][j]+TOT,st[i][j+1]+TOT,0);
                add(st[i][j]+tot+TOT,st[i][j+1]+tot+TOT,0);
                add(st[i][j]+TOT,st[i][j+1]+tot+TOT,dep[lca(t[st[i][j]],t[st[i][j+1]])]);
            }
        }
    }
    
    struct node {
        int v,d;
        node() {v=0,d=0;}
        node(int a,int b) {v=a,d=b;}
        bool operator <(const node &a)const {return d>a.d;}
    };
    priority_queue<node>q;
    
    bool vis[N];
    void dij() {
        memset(vis,0,sizeof(vis));
        while(!q.empty()) {
            node tem=q.top();q.pop();
            int v=tem.v;
            if(vis[v]) continue ;
            vis[v]=1;
            for(int i=h[v];i;i=s[i].next) {
                int to=s[i].to;
                if(vis[to]) continue ;
                if(dis[to]>dis[v]+s[i].c) {
                    dis[to]=dis[v]+s[i].c;
                    q.push(node(to,dis[to]));
                }
            }
        }
    }
    
    int main() {
        int T=Get();
        while(T--) {
            n=Get(),m=Get(),k=Get();
            Init();
            tot=m<<1,TOT=tot<<1;
            int a,b,c,d;
            for(int i=1;i<=m;i++) {
                a=Get(),b=Get(),c=Get(),d=Get();
                t[i]=t[i+m]=d;
                w[i]=w[i+TOT]=c;
                st[b].push_back(i);
                st[a].push_back(i+m);
                add(i+m+tot,i,w[i]);
                add(i+m+tot+TOT,i,w[i]);
                add(i+m+tot,i+TOT,w[i]);
                add(i+m+tot+TOT,i+TOT,w[i]);
            }
            for(int i=1;i<k;i++) {
                a=Get(),b=Get(),c=Get();
                e[a].push_back(b);
            }
            dfs(1);
            build();
            for(int i=0;i<st[1].size();i++) {
                if(st[1][i]>m) {
                    dis[st[1][i]-m]=dis[st[1][i]-m+TOT]=w[st[1][i]-m];
                    q.push(node(st[1][i]-m,w[st[1][i]-m]));
                    q.push(node(st[1][i]-m+TOT,w[st[1][i]-m]));
                }
            }
            dij();
            memset(ans,0x3f,sizeof(ans));
            for(int i=1;i<=n;i++) {
                for(int j=0;j<st[i].size();j++)
                    if(st[i][j]<=m) {
                        ans[i]=min(ans[i],min(dis[st[i][j]],dis[st[i][j]+TOT]));
                    }
            }
            for(int i=2;i<=n;i++) cout<<ans[i]<<"\n";
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hchhch233/p/10468062.html

[img]: /images/20211220/1773de60efe74e3bbbb3c930442f461a.png
[img 1]: /images/20211220/7bf40eff7b6f4b07a24faabed80583b2.png
[img 2]: /images/20211220/9261ae8edc72400e8d0b319f83c1aead.png
[img 3]: /images/20211220/d241646193c041dfb02e484ebf53a6b5.png
[Claris]: https://www.cnblogs.com/clrs97/p/7833797.html