NOI2018_Day1_T1

题目描述

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。魔力之都可以抽象成一个 n 个节点、m 条边的无向连通图（节点的编号从 1 至 n）。我们依次用 l,a 描述一条边的长度、海拔。作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。 Yazid 的家恰好在魔力之都的 1 号节点。对于接下来 Q 天，每一天 Yazid 都会告诉你他的出发点 v ，以及当天的水位线 p。每一天，Yazid 在出发点都拥有一辆 . 车。这辆车由于一些故障不能经过有积水的边。 Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 • 需要特殊说明的是，第二天车会被重置，这意味着： – 车会在新的出发点被准备好。 – Yazid 不能利用之前在某处停放的车。 Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。

上面是题目描述。

主要做法kruscal重构树，即在kruscal合并的时候新建一个父节点，点权为原边权，这样可以形成一个大（小）根堆。

然后两个点求lca可知最大边最小（最小边最大）。具体看程序。

代码：

#include<queue>

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 400005

#define M 800005

inline int rd()

{

    int f=,c=;char ch = getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){c=*c+ch-'';ch=getchar();}

    return f*c;

}

struct Node

{

    int u,v,l,a,nxt;

}w[M],e[*N];

struct Poi

{

    int x,d;

    Poi(){}

    Poi(int x,int d):x(x),d(d){}

    friend bool operator < (Poi a,Poi b)

    {

        return a.d>b.d;

    }

};

bool cmp(Node n1,Node n2)

{

    return n1.a>n2.a;

}

int T,n,m,ans,cnt,hed[N],q,k,s;

void ae(int f,int t,int l)

{

    e[++cnt].u = f;

    e[cnt].v = t;

    e[cnt].l=l;

    e[cnt].nxt = hed[f];

    hed[f]=cnt;

}

int dis[N];

bool vis[N];

priority_queue<Poi>que;

void dij()

{

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

    {

        dis[i]=0x3f3f3f3f;

        vis[i]=;

    }

    dis[]=;

    que.push(Poi(,));

    while(!que.empty())

    {

        Poi tp = que.top();

        que.pop();

        int u = tp.x;

        if(vis[u])continue;

        vis[u]=;

        for(int j=hed[u];j;j=e[j].nxt)

        {

            int to = e[j].v;

            if(dis[to]>dis[u]+e[j].l)

            {

                dis[to]=dis[u]+e[j].l;

                que.push(Poi(to,dis[to]));

            }

        }

    }

}

int fa[*N][],ff[*N],vl[*N],min_dis[*N],tot;

int findfa(int x)

{

    return ff[x]==x?x:ff[x]=findfa(ff[x]);

}

void kruskal()

{

    int ad = ;

    tot = n;

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

    {

        min_dis[i]=dis[i];

        ff[i]=i;

    }

    for(int i=;ad<n-;i++)

    {

        int u = w[i].u;

        int v = w[i].v;

        if(findfa(u)!=findfa(v))

        {

            ad++;

            tot++;

            fa[ff[u]][]=tot;

            fa[ff[v]][]=tot;

            min_dis[tot]=min(min_dis[ff[u]],min_dis[ff[v]]);

            vl[tot]=w[i].a;

            ff[tot]=tot;

            ff[ff[u]]=tot;

            ff[ff[v]]=tot;

        }

    }

}

int main()

{

    T=rd();

    while(T--)

    {

        n=rd(),m=rd(),ans=;

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

        cnt=;

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

        {

            w[i].u=rd(),w[i].v=rd(),w[i].l=rd(),w[i].a=rd();

            ae(w[i].u,w[i].v,w[i].l);

            ae(w[i].v,w[i].u,w[i].l);

        }

        dij();

        sort(w+,w++m,cmp);

        kruskal();

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

        {

            for(int i=;i<=tot;i++)

            {

                fa[i][j]=fa[fa[i][j-]][j-];

            }

        }

        q=rd(),k=rd(),s=rd();

        int v,p;

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

        {

            v = (rd()+k*ans-)%n+;

            p = (rd()+k*ans)%(s+);

            ans=dis[v];

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

            {

                if(vl[fa[v][j]]>p)

                {

                    ans=min_dis[fa[v][j]];

                    v=fa[v][j];

                }

            }

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

        }

    }

    return ;

}

巴特西

NOI2018_Day1_T1_归程

题目描述

最新文章

热门文章