NOI2018 归程

题面较长,就不摆出来了,看下面

题面

Solution

那么大概复述一下题目大意

n个点,m条边,保证图联通,每条边有两个权值,一个长度,一个海拔,多组询问,告诉你起点和水位线,小于等于水位线的边都会被淹没,只能走路,否则可以开车,问从当天起点到1号节点最少步行经过的长度,有些询问会强制在线

这道题是今年NOI的D1T1,当时在线打的时候,只打了个SPFA48分(直接跑),倍增优化60分

正解:Kruskal重构树/可持久化并查集

由于博主蒟蒻不会可持久化数据结构,所以讲Kruskal重构树

首先复习一下Kruskal最小生成树,是以并查集为辅助实现的,并通过路径压缩保证了时间复杂度,显然这样同时也会破坏树的原本的结构,但由于最小生成树不用保存这些信息,所以没什么影响,但Kruskal重构树就不同了....

Kruskal重构树的经典例题:给你一张图,每次询问两点之间所有简单路径中最大边权的最小值

常规做法,建出一棵最小生成树,答案就是树上的边权最小值

那么Kruskal重构树怎么做呢?
和kruskal类似,依然需要将边排序.
不同的是,我们建一个虚点,让两个联通快(查询的两个点的祖先)分别与虚点相连,这个虚点带有点权,点权就是本应相连的两个点之间的边权

这样的树有两个优雅的性质

1. 这是一颗二叉树，并且相当于一个堆，因为边是有顺序合并的.
2. 最小生成树上路径的边权信息转化成了点权信息.

那么刚才那道经典例题就变成了询问两点lca的权值

那么回看这道题,应该比较好理解了,因为要求边的海拔要大于水位线,所以把海拔从大到小排序,为什么是从大到小,因为这样海拔高的先合并,也就是树根的点权就是最小的边权,如果一个点的点权大于水位线,那么以它为根的子树也会大于水位线,那么我们就可以在它的子树中找到步行距离最小是多少
所以每次跳lca直到点权大于水位线

再复述一遍思路

1. 首先一遍dijkstra预处理出所有点到1的最短步行距离
2. 建出Kruskal重构树
3. dfs一遍\(O(n)\)处理处以Kruskal重构树的根为根的子树中到1点的最短步行距离
4. lca预处理
5. 求两点lca在线回答询问

提示1:因为我们已经建了虚点来连向两个联通快,所以路径压缩并不会破坏Kruskal重构树的结构,只会影响原树的结构

提示2:关于边和点的数组大小,每建一个虚点要建4条边,因为原图有M条边,所以建M个虚点,那么就要开\(M*4\)的数组,至于点,每两条边一个虚点,就是M/2个点加上原来有N个点

Code

#include<bits/stdc++.h>
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
using namespace std;
typedef long long lol;
const int N=200010,M=400010;

void in(int &ans)
{
    ans=0;int f=1;char i=getchar();
    while(i<'0' || i>'9') {if(i=='-') f=-1;i=getchar();}
    while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+(i^48),i=getchar();
    ans*=f;
}

int T,n,m,Q,k,s,cnt,tq;
lol to[M<<2],nex[M<<2],w[M<<2],h[M<<2],head[N<<1];
lol fa[N<<1],dp[N<<1],dis[N<<1],vis[N],f[20][N<<1],v[N<<1];

struct node {
    lol x,y,v,h;
}A[M];

struct Node{
    lol id,v;
    bool operator < (const Node &a) const {return v>a.v;}
};

inline void add(lol a,lol b,lol c,lol d)
{
    to[++cnt]=b,nex[cnt]=head[a];
    w[cnt]=c,h[cnt]=d,head[a]=cnt;
}

int find(int x) {
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}

bool cmp(node a,node b) {return a.h>b.h;}

void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<Node>q;
    Node tmp; tmp = (Node) {1,0};
    q.push(tmp); dis[1]=0;
    while(!q.empty()) {
    lol u=q.top().id; q.pop();
    if(vis[u]) continue; vis[u]=1;
    for(lol i=head[u];i;i=nex[i]) {
        if(dis[to[i]]>dis[u]+w[i]) {
        dis[to[i]]=dis[u]+w[i];
        tmp=(Node){to[i],dis[to[i]]};
        q.push(tmp);
        }
    }
    }
}

void init()
{
    for(lol i=1;i<=19;i++)
    for(lol j=1;j<=tq;j++)
    f[i][j]=f[i-1][f[i-1][j]];
}

void dfs(int u,int father)
{
    dp[u]=dis[u];
    for(lol i=head[u];i;i=nex[i]) {
    if(to[i]!=father) {
        f[0][to[i]]=u;
        dfs(to[i],u);
        dp[u]=Min(dp[u],dp[to[i]]);
    }
    }
}

lol lca(lol x,lol y) {
    for(lol i=19;i>=0;i--)
    if(v[f[i][x]]>y) x=f[i][x];
    return x;
}

int main()
{
    //freopen("return.in","r",stdin);
    //freopen("return.out","w",stdout);
    lol last; in(T);
    while(T--) {
    memset(head,0,sizeof(head));
    
    in(n), in(m), tq=n, last=cnt=0;
    
    for(int i=1;i<=m;i++) {
        int a, b, c, d;
        in(a), in(b), in(c), in(d);
        add(a,b,c,d), add(b,a,c,d);
        A[i] = (node) {a,b,c,d};
    }
    
    dijkstra();
    
    cnt=0; memset(head,0,sizeof(head));
    
    for(int i=1;i<=n;i++) fa[i]=i;
    
    sort(A+1, A+1+m, cmp);
    
    for(int i=1;i<=m;i++) {
        int fx = find(A[i].x),fy = find(A[i].y);
        if(fx == fy) continue;
        fa[fx] = ++tq, fa[fy] = tq, fa[tq] = tq, v[tq] = A[i].h;
        add(tq,fx,0,0), add(fx,tq,0,0);
        add(tq,fy,0,0), add(fy,tq,0,0);
    }
    
    dfs(tq,0); init();
    in(Q), in(k), in(s);
    /*for(int i=1;i<=tq;i++) cout<<dp[i]<<" ";
      cout<<endl;*/
    
    for(int i=1;i<=Q;i++) {
        int v,p; in(v), in(p);
        v=(v+k*last-1)%n+1, p=(p+k*last)%(s+1);
        printf("%lld\n",last=dp[lca(v,p)]);
    }
    }
    return 0;
}

博主蒟蒻,随意转载.但必须附上原文链接

http://www.cnblogs.com/real-l/

NOI2018 归程 [Kruskal重构树]

原文：https://www.cnblogs.com/real-l/p/9568354.html