JZOJ 3527.迷宫花坛(garden)

题面

思路

考场想到 (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
" , getans(x , y));
	}
}