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

最新文章

热门文章