bzoj3694: 最短路（树链剖分/并查集）

　　bzoj1576的帮我们跑好最短路版本23333（双倍经验！嘿嘿嘿

　　这题可以用树链剖分或并查集写。树链剖分非常显然，并查集的写法比较妙，涨了个姿势，原来并查集的路径压缩还能这么用...

　　首先对于不在最短路径树上的边x->y，设t为最短路径树上lca(x,y)，则t到y上的路径上的点i到根的距离都可以用h[x]+dis[x][y]+h[y]-h[i]（h[]为深度）来更新，因为h[i]一定，只要让h[x]+dis[x][y]+h[y]最小就行，这里用树剖直接修改整条链上的数，就可以过了。

　　并查集的方法就很巧妙了...把不在最短路径树上的边找出来，按照h[x]+dis[x][y]+h[y]从小到大排序。然后按排序后的边的顺序更新答案，被更新过了的必然不会被再次更新。更新的方法就是每次两个指针从x和y一步步向t靠近并更新沿途上没更新过的点，同时用并查集记录这些更改过的点的顶部，下次更新下面跑到这里的点直接就可以跳到没修改的地方。好像感觉其实就是把树剖改成用并查集来跳跳跳而已...

　　只写了并查集，树剖的下次补（QAQ模板都不会打了已经

　　UPD 2017.6.28：今天复习了下树剖，然后把这题写了嘿嘿嘿。这题最后只查询叶子结点，所以就不用上传了，非常好写。

树链剖分：

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=,inf=;

struct poi{int too,pre,sum;}e[maxn];

struct tjm{int sum,tag;}a[maxn];

struct zs{int x,y,len;}edge[maxn];

int n,m,x,y,z,flag,tot,tot2,cnt;

int last[maxn],size[maxn],fa[maxn],dep[maxn],son[maxn],w[maxn],top[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

void dfs1(int x)

{

    size[x]=;

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

    {

        int too=e[i].too;

        if(too!=fa[x])

        {

            fa[too]=x;

            dep[too]=dep[x]+e[i].sum;

            dfs1(too);

            if(size[too]>size[son[x]])son[x]=too;

            size[x]+=size[too];

        }

    }

}

void dfs2(int x,int tp)

{

    w[x]=++cnt;top[x]=tp;

    if(son[x])dfs2(son[x],tp);

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

    if(e[i].too!=son[x]&&e[i].too!=fa[x])

    dfs2(e[i].too,e[i].too);

}

void pushdown(int x)

{

    if(a[x].tag==inf)return;

    int tag=a[x].tag;a[x].tag=inf;

    a[x<<].tag=min(tag,a[x<<].tag);

    a[x<<|].tag=min(tag,a[x<<|].tag);

}

void update(int x,int nl,int nr,int l,int r,int delta)

{

    ///if(nl!=nr)pushdown(x);

    if(l<=nl&&nr<=r)a[x].tag=min(a[x].tag,delta);

    else

    {

        //printf("%d %d\n",nl,nr);

        int mid=(nl+nr)>>;

        if(l<=mid)update(x<<,nl,mid,l,r,delta);

        if(r>mid)update(x<<|,mid+,nr,l,r,delta);

    }

}

ll query(int x,int nl,int nr,int num)

{

    if(nl!=nr)pushdown(x);

    if(nl==num&&nr==num)return a[x].tag;

    else

    {

        int mid=(nl+nr)>>;

        if(nl<=num&&num<=mid)return query(x<<,nl,mid,num);

        if(mid<num&&num<=nr)return query(x<<|,mid+,nr,num);

    }

}

void work(int x,int y,int len)

{

    int f1=top[x],f2=top[y];

    while(f1!=f2)

    {

        if(dep[f1]<dep[f2])swap(x,y),swap(f1,f2);

        update(,,cnt,w[f1],w[x],len);

        x=fa[f1];f1=top[x];

    }

    if(x==y)return;

    if(dep[x]<dep[y])swap(x,y);

    update(,,cnt,w[son[y]],w[x],len);

}

void build(int x,int l,int r)

{

    a[x].tag=inf;int mid=(l+r)>>;

    if(l!=r)build(x<<,l,mid),build(x<<|,mid+,r);

}

int main()

{

    read(n);read(m);

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

    {

        read(x);read(y);read(z);read(flag);

        if(!flag)edge[++tot2].x=x,edge[tot2].y=y,edge[tot2].len=z;

        else add(x,y,z),add(y,x,z);

    }

    dfs1();dfs2(,);build(,,n);

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

    work(edge[i].x,edge[i].y,edge[i].len+dep[edge[i].x]+dep[edge[i].y]);

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

    {

        int ans=query(,,cnt,w[i]);

        if(ans!=inf)printf("%d ",ans-dep[i]);

        else printf("-1 ");

    }

    return ;

}

并查集：

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

const int maxn=;

struct zs{int too,sum,pre;}e[];

struct poi{int x,y,len;}edge[];

int n,m,x,y,z,flag,tot,tot2;

int fq[maxn],fa[maxn],h[maxn],v[maxn],last[maxn];

void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

void dfs(int x,int fa)

{

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

    if(e[i].too!=fa)h[e[i].too]=h[x]+e[i].sum,fq[e[i].too]=x,dfs(e[i].too,x);

}

bool cmp(poi a,poi b){return a.len<b.len;}

int gf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);}

int main()

{

    read(n);read(m);

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

    {

        read(x);read(y);read(z);read(flag);

        if(flag)add(x,y,z),add(y,x,z);

        else edge[++tot2].x=x,edge[tot2].y=y,edge[tot2].len=z;

    }

    dfs(,);

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

    edge[i].len+=h[edge[i].x]+h[edge[i].y];

    sort(edge+,edge++tot2,cmp);

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

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

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

    {

        int x=gf(edge[i].x),y=gf(edge[i].y);

        while(x!=y)

        {

            if(h[x]<h[y])swap(x,y);

            if(!v[x])v[x]=i;

            x=fq[x]=gf(fq[x]);

        }

    }

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

    if(v[i])printf("%d ",edge[v[i]].len-h[i]);

    else printf("-1 ");

}

巴特西

bzoj3694: 最短路（树链剖分/并查集）

最新文章

热门文章