BZOJ 5415: [Noi2018]归程 kruskal重构树

title

\(~\)
BZOJ 5415
LUOGU 4768
题目好长呢，不想贴了。。

analysis

两个小感慨：

1. 听说因为这道题，有些大佬 \(Ag\to Cu\)，就是因为用了 \(spfa\)，所以，以后遇到无负边图，还是用 \(Dijkstra\)吧。
2. \(kruskal\)重构树其实算是属于冷僻知识点的吧，\(BZOJ\) 上也只有 \(Network\) 提到了这种算法，所以学习算法真的要认真，并且这时候，刷题量就代表些东西了。

正式说题解：
这道题要用 \(kruskal\)重构树，为什么？性质使然。\(kruskal\)重构树 有以下几个好性质：

• 树上除叶子结点以外的点都对应着原来生成树中的边，叶子结点是原生成树上的节点。
• 由于新点的创建顺序与原来生成树上边权的大小有关，可以发现，从每个点到根节点上（除叶子结点外）按顺序访问到的点的点权是 单调 的。
• 出于 \(kruskal\) 算法贪心的性质，两个点 \(x\) 和 \(y\) 的 \(lca\) 的点权就对应着它们最小生成树上的瓶颈。
• 实际上这棵树就是一个二叉堆。

那么这道题怎么构造 \(kruskal\)重构树 ？
最短路把长度搞定了，那么还剩下海拔，就用这个搞定喽，以海拔为第一关键字对边进行从大到小的排序，修建 \(kruskal\)重构树。

对于每一棵子树，如果询问中的水位线是低于子树的根节点的，那么此时这棵子树中的所有叶子结点都是连通的。也就是说这颗子树中任选一个点出发，到子树中的其它点都不需要花费。

假设对于当前询问，我们找到了一个子树的根节点 \(x\)（满足 \(d[x]>p\)且 \(d[fa[x]]<=p\) 且出发点 \(y\) 在子树中），这时从 \(y\) 出发可以直接抵达子树中的任意一个叶子结点。

因此我们需要从众多叶子节点中选出一个距离 1 号点花费最小的，所以这个就用 \(Dijkstra\) 处理出所有点到 1 好点的最小花费，这道题就算完了。

完整的从前到后的思路，请参照 ldxcaicai 的了，嘻嘻：
然后再捋一捋思路。

1. 我们首先要求出每个点到 1 号点的最小花费，这个直接 \(Dijsktra+\)最短路预处理。
2. 然后是要建出 \(kruskal\)重构树，再然后维护以每个点作为根节点时子树中距离 1 号点的最小花费，这个建完树后一个简单的 \(dfs\) 搞定。
3. 最后是如何找到点 \(x\)，这时我们要让一个重要的算法登场：倍增算法。直接加上点权 \(>p\) 的限制在树上倍增即可。

code

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn=4e5+10,maxm=8e5+10,inf=0x3f3f3f3f;

char buf[1<<15],*fs,*ft;
inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
template<typename T>inline void read(T &x)
{
    x=0;
    T f=1, ch=getchar();
    while (!isdigit(ch) && ch^'-') ch=getchar();
    if (ch=='-') f=-1, ch=getchar();
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}

char Out[1<<24],*fe=Out;
inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
template<typename T>inline void write(T x)
{
    if (!x) *fe++=48;
    if (x<0) *fe++='-', x=-x;
    T num=0, ch[20];
    while (x) ch[++num]=x%10+48, x/=10;
    while (num) *fe++=ch[num--];
    *fe++='\n';
}

int vc[maxm<<1],Nc[maxm<<1],hc[maxn<<1],lc;
inline void addc(int x,int y)
{
    vc[++lc]=y,Nc[lc]=hc[x],hc[x]=lc;
}

struct Orz{int x,y,l,a;}e[maxm],p[maxn<<1];
inline bool cmp(Orz c,Orz d)
{
    return c.a>d.a;
}

int fa[maxn<<1];
inline int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);
}

int n,m,cnt,sum;
inline void Kruskal()
{
    cnt=n,sum=0;
    for (int i=1; i<=(n<<1); ++i) fa[i]=i;
    sort(e+1,e+m+1,cmp);
    for (int i=1; i<=m; ++i)
    {
        int x=get(e[i].x),y=get(e[i].y);
        if (x==y) continue;
        addc(++cnt,x),addc(cnt,y);
        fa[x]=fa[y]=cnt;
        p[cnt].a=e[i].a;
        if (++sum==n-1) break;
    }
}

int ver[maxm],edge[maxm],Next[maxm],head[maxn],len;
inline void add(int x,int y,int z)
{
    ver[++len]=y,edge[len]=z,Next[len]=head[x],head[x]=len;
    ver[++len]=x,edge[len]=z,Next[len]=head[y],head[y]=len;
}

int dist[maxn];
bool vis[maxn];
inline void Dijkstra(int s)
{
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis));
    priority_queue<pii,vector<pii>,greater<pii> >q;
    q.push(make_pair(0,s)),dist[s]=0;
    while (!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        for (int i=head[x]; i; i=Next[i])
        {
            int y=ver[i],z=edge[i];
            if (dist[y]>dist[x]+z)
            {
                dist[y]=dist[x]+z;
                q.push(make_pair(dist[y],y));
            }
        }
    }
    for (int i=1; i<=n; ++i) p[i].l=dist[i];
}

int f[maxn][20],d[maxn];
inline void dfs(int x,int pa)
{
    d[x]=d[pa]+1,f[x][0]=pa;
    for (int i=1; i<=19; ++i) f[x][i]=f[f[x][i-1]][i-1];
    for (int i=hc[x]; i; i=Nc[i])
    {
        int y=vc[i];
        dfs(y,x);
        p[x].l=min(p[x].l,p[y].l);
    }
}

inline int query(int x,int y)
{
    for (int i=19; i>=0; --i)
        if (d[x]-(1<<i)>0 && p[f[x][i]].a>y) x=f[x][i];
    return p[x].l;
}

inline void Clear()
{
    memset(f,0,sizeof(f));
    memset(d,0,sizeof(d));
    memset(head,0,sizeof(head));
    memset(hc,0,sizeof(hc));
    len=lc=0;
}

int main()
{
    int T;read(T);
    while (T--)
    {
        Clear();
        read(n);read(m);
        for (int i=1; i<=m; ++i) read(e[i].x),read(e[i].y),read(e[i].l),read(e[i].a),add(e[i].x,e[i].y,e[i].l);
        for (int i=n+1; i<=(n<<1); ++i) p[i].l=inf;
        Dijkstra(1);
        int Q,K,S;
        read(Q);read(K);read(S);
        Kruskal();
        dfs(cnt,0);
        int lastans=0;
        while (Q--)
        {
            int v,p;read(v);read(p);
            int x=(v+lastans*K-1)%n+1,y=(p+lastans*K)%(S+1);
            write(lastans=query(x,y));
        }
    }
    flush();
    return 0;
}

BZOJ 5415: [Noi2018]归程 kruskal重构树

原文：https://www.cnblogs.com/G-hsm/p/11318201.html