题面

思路

考场想到 \(tarjan\) 缩点

然而忘了缩点怎么打

于是甩了个暴力

改题时学了个圆方树

发现挺好用

于是······注意重边
\(Code\)

#include<cstdio>

#include<iostream>

#include<cmath>

#include<map>

using namespace std;

const int N = 3e5 + 5;

int n , m , q , cnt , tot1 , tot2 , top , dfc;

int p[N][2] , h1[N] , h2[N] , dfn[N] , low[N] , df[N] , f[N][22] , fa[N][22] , dep[N];

map<pair<int , int> , int> mp;

struct edge1{

	int nxt , to , w;

}e1[N * 2];

struct edge2{

	int nxt , to , w;

}e2[N * 2];

struct node{

	int x , z;

}stack[N];

void add1(int x , int y , int z)

{

	e1[++tot1] = edge1{h1[x] , y , z};

	h1[x] = tot1;

}

void add2(int x , int y , int z)

{

	e2[++tot2] = edge2{h2[x] , y , z};

	h2[x] = tot2;

}

void tarjan(int x , int fa , int z)

{

	stack[++top] = node{x , z};

	low[x] = dfn[x] = ++dfc;

	for(register int i = h1[x]; i; i = e1[i].nxt)

	{

		int v = e1[i].to;

		if (!dfn[v])

		{

			tarjan(v , x , e1[i].w) , low[x] = min(low[x] , low[v]);

			if (dfn[x] < low[v]) add2(x , v , e1[i].w) , df[v] = e1[i].w , --top;

			else if (dfn[x] == low[v])

			{

				int BBC = 0 , tp = top;

				for(register int j = h1[x]; j; j = e1[j].nxt)

				if (e1[j].to == stack[top].x){BBC = e1[j].w; break;}

				add2(x , ++cnt , 0);

				while (stack[tp].x != x) df[stack[tp].x] = BBC , BBC += stack[tp].z , --tp;

				while (stack[top].x != x)

					add2(cnt , stack[top].x , min(df[stack[top].x] , BBC - df[stack[top].x])) , --top;

				df[cnt] = BBC;

			}

		}

		else if (v != fa) low[x] = min(low[x] , dfn[v]);

	}

}

void dfs(int x , int d)

{

	dep[x] = d;

	for(register int i = 1; i <= 20; i++)

	if (fa[x][i - 1]) fa[x][i] = fa[fa[x][i - 1]][i - 1] , f[x][i] = f[x][i - 1] + f[fa[x][i - 1]][i - 1];

	else break;

	for(register int i = h2[x]; i; i = e2[i].nxt)

	{

		fa[e2[i].to][0] = x , f[e2[i].to][0] = e2[i].w;

		dfs(e2[i].to , d + 1);

	}

}

int getans(int x , int y)

{

	int u = x , v = y;

	if (dep[u] < dep[v]) swap(u , v);

	int deep = dep[u] - dep[v] , res = 0;

	for(register int i = 0; i <= 20; i++)

	if (deep & (1 << i)) res += f[u][i] , u = fa[u][i];

	if (u == v) return res;

	for(register int i = 20; i >= 0; i--)

	if (fa[u][i] != fa[v][i]) res += f[u][i] + f[v][i] , u = fa[u][i] , v = fa[v][i];

	if (fa[u][0] <= n) return res + f[u][0] + f[v][0];

	return res + min(abs(df[u] - df[v]) , df[fa[u][0]] - abs(df[u] - df[v]));

}

int main()

{

	freopen("garden.in" , "r" , stdin);

	freopen("garden.out" , "w" , stdout);

	scanf("%d%d" , &n , &m);

	int x , y , z;

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

	{

		scanf("%d%d%d" , &x , &y , &z);

		if (x > y) swap(x , y);

		p[i][0] = x , p[i][1] = y;

		if (mp[make_pair(x , y)] == 0) mp[make_pair(x , y)] = z;

		else mp[make_pair(x , y)] = min(mp[make_pair(x , y)] , z);

	}

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

	{

		x = p[i][0] , y = p[i][1] , z = mp[make_pair(x , y)];

		add1(x , y , z) , add1(y , x , z);

	}

	cnt = n;

	tarjan(1 , 0 , 0);

	dfs(1 , 0);

	scanf("%d" , &q);

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

	{

		scanf("%d%d" , &x , &y);

		printf("%d\n" , getans(x , y));

	}

}
巴特西

JZOJ 3527.迷宫花坛(garden)

题面

思路

\(Code\)

最新文章

热门文章
