洛谷 P4768 [NOI2018]归程

洛谷

361行代码的由来

数据分治大发好啊～

NOI的签到题，可怜我在家打了一下午才搞了80分。

正解应该是kruskal重构树或排序+可持久化并查集。

我就分点来讲暴力80分做法吧(毕竟正解我也没太懂)～

前6个点

这6个点有两种做法：

法1：最短路。

这6个点都是离线的，而且只有一种海拔，所以直接最短路。

跑完之后，直接判断海拔与水位，输出即可。

不过这些分也并不好拿，spfa会被卡，要用堆优化dijkstra。

法2：离线排序+并查集。

其实这个暴力思想就是正解思想了，很好想到的。

首先跑个最短路求一下1号点到所有点的距离，按照边权从大到小排序，对于询问也按照水位线从大到小排一下序。

显然，当一条边加入以后，就不可能再删除，因为水位线只会慢慢降低。

这样这个问题就可以转化成，当前询问下，如果把所有大于当前水位线的边加入图中，那么从起点出发，求它所能到达的点中与1号点距离最小的点即可。

加边时用并查集维护一下即可：

即对于两个点a，b在并查集中的祖先x，y，如果dis[x]>dis[y]，则令fa[x]=y。

这样并查集在查询时，就可以以常数的复杂度找到当前询问下的答案。注意加边是在一个查询开始前，将所有海拔大于水位线的边加进去。

树和链的5个点

这里我们可以考虑倍增。

预处理3个ST表：dpt[][]，num[][]，xiao[][]

分别表示从x点跳\(2^j\)步，从x到向上\(2^j\)个点的花费，最后是从x到向上\(2^j\)个点中海拔最小的点。

所以算法也很简单，先调到海拔最小的点，然后再倍增求花费。

当然也可以用之前讲的离线排序+并查集。

3个离线大点

直接按上面说的离线并查集即可。

15和16两个在线小点

离线并查集不管用了？别担心。

因为数据范围小，直接在线，每次询问用一个新的并查集维护。

反正能过。

超长代码菌～

请忽略代码中的正解部分，啦啦啦～

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long,int> Pair;

void read(int &aa)

{

    aa=0;char c=getchar();bool f=0;

    while (c>'9'||c<'0') {if (c=='-') f=1;c=getchar();}

    while (c>='0'&&c<='9')

        aa=(aa<<3)+(aa<<1)+(c^48),c=getchar();

    (f)&&(aa=-aa);

}

const int N=800020;

int n,m,q,k,s;

struct Edge {

    int next,cost,high,to;

}e[N<<2];

int last[N],spfaflag;

void add(int x,int y,int c,int h)

{

    e[++last[0]].to=y;

    e[last[0]].cost=c;e[last[0]].next=last[x];

    e[last[0]].high=h;last[x]=last[0];

}

int vis[N];

long long dis[N];

queue <int> Q;

priority_queue< Pair,vector<Pair>,greater<Pair> >que;

void spfa()

{

    while (!Q.empty()) Q.pop();

    for (int i=1;i<=n;++i) dis[i]=2e9+1;

    memset(vis,0,sizeof(vis));

    vis[1]=1;Q.push(1);dis[1]=0;

    while (!Q.empty()) {

        int x=Q.front();Q.pop();vis[x]=0;

        for (int i=last[x];i;i=e[i].next) {

            int y=e[i].to,c=e[i].cost;

            if (dis[y]>dis[x]+c) {

                dis[y]=dis[x]+c;

                if (!vis[y]) vis[y]=1,Q.push(y);

            }

        }

    }

}

void dijsktra()

{

    while (!que.empty()) que.pop();

    for (int i=1;i<=n;++i) dis[i]=2e9+1;

    memset(vis,0,sizeof(vis));

    dis[1]=0;

    que.push(make_pair(dis[1],1));

    while (!que.empty()) {

        Pair now=que.top();que.pop();

    	if (vis[now.second]) continue;

    	vis[now.second]=1;

   		for (int i=last[now.second];i;i=e[i].next)

    	if (dis[now.second]+e[i].cost<dis[e[i].to]) {

      		dis[e[i].to]=dis[now.second]+e[i].cost;

      		if (!vis[e[i].to]) que.push(make_pair(dis[e[i].to],e[i].to));

    	}

    }

}

int bian[N],gao[N];

void chain()

{

    int ed,pp,chainflag;

    long long ans,preans=0;

    read(q);read(k);read(s);

    for (int i=1;i<=q;++i) {

        chainflag=ans=0;

        read(ed);read(pp);

        ed=(ed+k*preans-1)%n+1;

        pp=(pp+k*preans)%(s+1);

        for (int t=ed;t>1;--t)

            if (chainflag||gao[t]<=pp)

                ans+=bian[t],chainflag=1;

        printf("%lld\n",ans);

        preans=ans;

    }

}

int dep[N],dpt[N][33],xiao[N][33],num[N][33];

void dfs(int x,int d)

{

    dep[x]=d;

    for (int i=last[x];i;i=e[i].next) {

        int y=e[i].to;

        if (!dep[y]) {

            dpt[y][0]=x;

            xiao[y][0]=e[i].high;

            num[y][0]=e[i].cost;

            dfs(y,d+1);

        }

    }

}

void init()

{

    for (int j=1;j<=24;++j)

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

            dpt[i][j]=dpt[dpt[i][j-1]][j-1];

            xiao[i][j]=min(xiao[i][j-1],xiao[dpt[i][j-1]][j-1]);

            num[i][j]=num[i][j-1]+num[dpt[i][j-1]][j-1];

        }

}

int zuo(int x,int gaodu)

{

    int ans=0;

    for (int j=24;j>=0;--j) {

        if (xiao[x][j]>gaodu&&dpt[x][j])

            x=dpt[x][j];

    }

    if (x!=1) {

        for (int j=24;j>=0;--j)

            if (dpt[x][j])

                ans+=num[x][j],x=dpt[x][j];

        return ans;

    }

    return 0;

}

void tree()

{

    int ed,pp;

    dfs(1,1);init();

    read(q);read(k);read(s);

    int ans,preans=0;

    for (int i=1;i<=q;++i) {

        read(ed);read(pp);

        ed=(ed+k*preans-1)%n+1;

        pp=(pp+k*preans)%(s+1);ans=zuo(ed,pp);

        printf("%d\n",ans);preans=ans;

    }

}

struct Line {

    int from,to,cost,high;

}line[N<<1];

struct ask {

    int shui,id,v,res;

}wen[N];

int baba[N];

bool pai1(ask t1,ask t2)

{

    return t1.shui>t2.shui;

}

bool pai2(Line t1,Line t2)

{

    return t1.high>t2.high;

}

bool pai3(ask t1,ask t2)

{

    return t1.id<t2.id;

}

int find(int x)

{

    return x!=baba[x]?baba[x]=find(baba[x]):x;

}

void unionset(int x,int y)

{

    int u=find(x),v=find(y);

    if (u==v) return;

    if (dis[u]>dis[v]) baba[u]=v;

    else baba[v]=u;

}

void outline()

{

    for (int i=1;i<=q;++i) {

        read(wen[i].v);read(wen[i].shui);

        wen[i].id=i;

    }

    sort(&wen[1],&wen[1+q],pai1);

    sort(&line[1],&line[1+m],pai2);

    for (int i=1;i<=n;++i) baba[i]=i;

    int now=1;

    for (int i=1;i<=q;++i) {

        while (now<=m&&line[now].high>wen[i].shui)

            unionset(line[now].from,line[now].to),++now;

        wen[i].res=dis[find(wen[i].v)];

    }

    sort(wen+1,wen+1+q,pai3);

    for (int i=1;i<=q;++i) printf("%d\n",wen[i].res);

}

void navi_inline()

{

    int lastans=0,instead;

    sort(line+1,line+1+m,pai2);

    for (int j=1;j<=q;++j) {

        for (int i=1;i<=n;++i) baba[i]=i;

        int now=1;

        read(instead);

        int v=(instead+k*lastans-1)%n+1;

        read(instead);

        int p=(instead+k*lastans)%(s+1);

        while (now<=m&&line[now].high>p)

            unionset(line[now].from,line[now].to),++now;

        lastans=dis[find(v)];

        printf("%d\n",lastans);

    }

}

bool cmp(Line t1,Line t2)

{

    return t1.high>t2.high;

}

Line line2[N<<1];

int fa[N],ceng[N],tiao[N][25];

struct eeee {

    int to,next;

}ee[N<<1];

int head[N];

void jia(int x,int y)

{

    ee[++head[0]].to=y;ee[head[0]].next=head[x];

    head[x]=head[0];

}

void shensou(int x,int pa)

{

    ceng[x]=ceng[pa]+1,tiao[x][0]=pa;

    for (int i=1;i<=24;++i)

        tiao[x][i]=tiao[tiao[x][i-1]][i-1];

    for (int i=head[x];i;i=ee[i].next) {

        int y=ee[i].to;

        shensou(y,x);

        line2[x].cost=min(line2[x].cost,line2[y].cost);

    }

}

int xunwenta(int x,int y)

{

    for (int i=24;i>=0;--i)

        if (ceng[x]-(1<<i)>0&&line2[tiao[x][i]].high>y)

            x=tiao[x][i];

    return line2[x].cost;

}

int find2(int x)

{

    return x==fa[x]?x:fa[x]=find2(fa[x]);

}

void zhengjie_wo_wu_di_la_hahaha_kruskal()

{

    int tott=0,cntt=n;

    for (int i=1;i<=(n<<1);++i) fa[i]=i;

    sort(line+1,line+m+1,cmp);

    for (int i=1;i<=m;++i) {

        int u=line[i].from,v=line[i].to;

        int fx=find2(u),fy=find2(v);

        if (fx!=fy) {

            jia(++cntt,fx);

            jia(cntt,fy);

            fa[fx]=cntt;

            fa[fy]=cntt;

            line2[cntt].high=line[i].high;

            ++tott;

        }

        if (tott+1==n) break;

    }

    int lastans=0;

    shensou(cntt,0);

    int tttt;

    while (q--) {

        read(tttt);

        int x=(k*lastans+tttt-1)%n+1;

        read(tttt);

        int y=(k*lastans+tttt)%(s+1);

        printf("%d\n",lastans=xunwenta(x,y));

    }

}

int main()

{

    int T,x,y,c,h;read(T);

    while (T--) {

        memset(last,0,sizeof(last));

        memset(gao,0,sizeof(gao));

        memset(bian,0,sizeof(bian));

        memset(dep,0,sizeof(dep));

        memset(dpt,0,sizeof(dpt));

        memset(xiao,0,sizeof(xiao));

        memset(num,0,sizeof(num));

        memset(head,0,sizeof(head));

        memset(tiao,0,sizeof(tiao));

        read(n);read(m);bool flag=1;

        int pre=0,mp=2;

        for (int i=1;i<=m;++i) {

            read(x);read(y);read(c);read(h);

            gao[y]=h;bian[y]=c;

            if (x+1!=y) flag=0;

            if (pre!=h) --mp,pre=h;

            add(x,y,c,h);add(y,x,c,h);

            line[i].from=x;line[i].to=y;

            line[i].cost=c;line[i].high=h;

        }

        if (mp==1) {

            int ed,pp;

            read(q);read(k);read(s);dijsktra();

            for (int i=1;i<=q;++i) {

                spfaflag=0;

                read(ed);read(pp);

                ed=(ed-1)%n+1;pp=pp%(s+1);

                if (pp>=pre) spfaflag=1;

                printf("%lld\n",!spfaflag?dis[1]:dis[ed]);

            }

            continue;

        }

        if (m+1==n) {

            if (flag) chain();

            else tree();

            continue;

        }

        read(q);read(k);read(s);

        if (!k) {

            dijsktra();

            outline();

            continue;

        }

        if (k&&n<=1500) {

            dijsktra();

            navi_inline();

            continue;

        }

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

            line2[i].cost=0x3f3f3f3f;

        dijsktra();

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

            line2[i].cost=dis[i];

        zhengjie_wo_wu_di_la_hahaha_kruskal();

    }

    return 0;

}

巴特西