description

给一个N个点M条边的连通无向图，满足每条边最多属于一个环，有Q组询问，每次询问两点之间的最短路径。

analysis

建出圆方树后，可以知道仙人掌上每一个方点连着的边双其实就是一个简单环
\(tarjan\)缩环的时候可以先弄出每个环的边权和并做一个前缀和，这样环中两点距离就可求
设\(dis[i]\)表示从根节点到\(i\)节点的最小值，若\(x,y\)两点\(LCA\)是原点，则可以直接求
若为方点则表示\(x,y\)距离\(LCA\)最近的祖先是环上不相邻两点，只需要再判断环上这两点最短距离即可

code

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<map>
#define MAXN 100005
#define MAXM 200005
#define ll long long
#define reg register ll
#define max(x,y) ((x>y)?(x):(y))
#define min(x,y) ((x<y)?(x):(y))
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)
#define rep(i,a) for (reg i=las[a];i;i=nex[i])

using namespace std;

ll anc[MAXN][16];
ll las[MAXM],nex[MAXM],tov[MAXM],len[MAXM];
ll dfn[MAXN],low[MAXN],stack[MAXN];
ll fa[MAXN],sum[MAXN],dep[MAXN],dis[MAXN],size[MAXN];
ll n,m,q,nn,tot,tot1,num,top;
map<ll,ll>mp[MAXN],c[MAXN];
vector<ll>v[MAXN];

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void link(ll x,ll y,ll z){nex[++tot]=las[x],las[x]=tot,tov[tot]=y,len[tot]=z;}
inline void tarjan(ll x)
{
    dfn[x]=low[x]=++tot,stack[++top]=x;
    rep(i,x)if (!dfn[tov[i]])
    {
        tarjan(tov[i]),low[x]=min(low[x],low[tov[i]]);
        if (low[tov[i]]>=dfn[x])
        {
            ll tmp=0,last=0;++n;
            while (tmp!=tov[i])
            {
                last=tmp,tmp=stack[top--];
                v[n].push_back(tmp),v[tmp].push_back(n);

                size[n]+=last==0?mp[tmp][x]:mp[tmp][last];
                c[n][tmp]=size[n];
            }
            v[n].push_back(x),v[x].push_back(n);
            size[n]+=mp[x][tmp],c[n][x]=size[n];
        }
    }
    else low[x]=min(low[x],dfn[tov[i]]);
}
inline ll query(ll pos,ll x,ll y)
{
    ll tmp=abs(c[pos][x]-c[pos][y]);
    return min(tmp,size[pos]-tmp);
}
inline void dfs(ll x,ll y)
{
    anc[x][0]=y,dep[x]=dep[y]+1;
    fo(i,1,15)anc[x][i]=anc[anc[x][i-1]][i-1];
    if (x<=nn)
    {
        ll ff=anc[y][0];
        dis[x]=x==1?0:dis[ff]+query(y,x,ff);
    }
    fo(i,0,v[x].size()-1)if (v[x][i]!=y)dfs(v[x][i],x);
}
inline ll lca(ll x,ll y)
{
    if (dep[x]<dep[y])swap(x,y);
    fd(i,15,0)if (dep[anc[x][i]]>=dep[y])x=anc[x][i];
    if (x==y)return x;
    fd(i,15,0)if (anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
    return anc[x][0];
}
inline ll get(ll x,ll y,ll z)
{
    ll ans=dis[x]+dis[y];
    fd(i,15,0)
    {
        if (dep[anc[x][i]]>dep[z])x=anc[x][i];
        if (dep[anc[y][i]]>dep[z])y=anc[y][i];
    }
    return ans-dis[x]-dis[y]+query(z,x,y);
}
int main()
{
    //freopen("T2.in","r",stdin);
    //freopen("T2.out","w",stdout);
    n=nn=read(),m=read(),q=read();
    fo(i,1,m)
    {
        ll x=read(),y=read(),z=read();
        link(x,y,z),link(y,x,z),mp[x][y]=mp[y][x]=z;
    }
    tarjan(1),dfs(1,0);
    while (q--)
    {
        ll x=read(),y=read(),LCA=lca(x,y);
        printf("%lld\n",LCA<=nn?dis[x]+dis[y]-2*dis[LCA]:get(x,y,LCA));
    }
    return 0;
}

两点

【JZOJ1914】【BZOJ2125】最短路

description

analysis

code