BZOJ1977或洛谷4180 [BJWC2010]次小生成树

一道LCA+生成树

回到正题，我们先求出随便一棵最小生成树（设边权和为\(s\)），然后扫描剩下所有边，设扫到的边的两端点为\(x,y\)，长度为\(z\)，树上\(x,y\)间边权最大的边和严格次大的边分别为\(dis_1,dis_2\)。

如果\(z>dis_1\)，那么这条边可以替换掉\(dis_1\)对应的边，则得到一个可能答案\(s-dis_1+z\)。

如果\(z=dis_1\)，那么这条边可以替换掉\(dis_2\)对应的边，则得到一个可能答案\(s-dis_2+z\)。

然后我们就可以用倍增\(LCA\)快速求树上\(x,y\)间边权最大的边和严格次大的边，定义数组\(g[x][k][0],g[x][k][1]\)表示从节点\(x\)往上跳\(2^k\)下所经过的路径的最大值和严格次小值，然后在预处理\(LCA\)的同时处理即可。

因为调到心态爆炸，所以代码可能比较丑。。

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

const int M = 3e5 + 10;

const int K = 17;

struct dd {

	int x, y, z;

};

dd a[M];

struct aw {

	int ma, se_ma;

	aw()

	{

		ma = se_ma = 0;

	}

};

int fi[N], di[N << 1], da[N << 1], ne[N << 1], f[N][K], g[N][K][2], de[N], fa[N], l, gn;

bool v[M];

int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c<'0' || c>'9'; c = getchar())

		p |= c == '-';

	for (; c >= '0'&&c <= '9'; c = getchar())

		x = x * 10 + (c - '0');

	return p ? -x : x;

}

int comp(dd x, dd y)

{

	return x.z < y.z;

}

inline void sw(int &x, int &y)

{

	int z = x;

	x = y;

	y = z;

}

inline int maxn(int x, int y)

{

	return x > y ? x : y;

}

inline ll minn(ll x, ll y)

{

	return x < y ? x : y;

}

inline int fin(int x)

{

	if (!(fa[x] ^ x))

		return x;

	return fa[x] = fin(fa[x]);

}

inline void add(int x, int y, int z)

{

	di[++l] = y;

	da[l] = z;

	ne[l] = fi[x];

	fi[x] = l;

}

void dfs(int x)

{

	int i, y;

	for (i = 1; i <= gn; i++)

	{

		f[x][i] = f[f[x][i - 1]][i - 1];

		g[x][i][0] = maxn(g[x][i - 1][0], g[f[x][i - 1]][i - 1][0]);

		g[x][i][1] = !(g[x][i - 1][0] ^ g[f[x][i - 1]][i - 1][0]) ? maxn(g[x][i - 1][1], g[f[x][i - 1]][i - 1][1]) : (g[x][i - 1][0] > g[f[x][i - 1]][i - 1][0]) ? maxn(g[x][i - 1][1], g[f[x][i - 1]][i - 1][0]) : maxn(g[x][i - 1][0], g[f[x][i - 1]][i - 1][1]);

	}

	for (i = fi[x]; i; i = ne[i])

	{

		y = di[i];

		if (!de[y])

		{

			de[y] = de[x] + 1;

			f[y][0] = x;

			g[y][0][0] = da[i];

			g[y][0][1] = -1e9;

			dfs(y);

		}

	}

}

aw fx(aw X, int i, int x)

{

	if (X.ma < g[x][i][0])

	{

		X.se_ma = maxn(X.ma, g[x][i][1]);

		X.ma = g[x][i][0];

	}

	else

		if (X.ma > g[x][i][0])

			X.se_ma = maxn(g[x][i][0], g[x][i][1]);

	return X;

}

aw lca(int x, int y)

{

	int i;

	aw X;

	if (de[x] > de[y])

		sw(x, y);

	for (i = gn; ~i; i--)

		if (de[f[y][i]] >= de[x])

		{

			X = fx(X, i, y);

			y = f[y][i];

		}

	if (!(x^y))

		return X;

	for (i = gn; ~i; i--)

		if (f[x][i] ^ f[y][i])

		{

			X = fx(X, i, x);

			X = fx(X, i, y);

			x = f[x][i];

			y = f[y][i];

		}

	X = fx(X, 0, x);

	return X;

}

int main()

{

	int i, k = 0, n, m, x, y;

	ll s = 0, mi = 1e18;

	n = re();

	m = re();

	gn = log2(n);

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

		fa[i] = i;

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

	{

		a[i].x = re();

		a[i].y = re();

		a[i].z = re();

	}

	sort(a + 1, a + m + 1, comp);

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

	{

		x = fin(a[i].x);

		y = fin(a[i].y);

		if (x^y)

		{

			fa[y] = x;

			k++;

			s += a[i].z;

			add(a[i].x, a[i].y, a[i].z);

			add(a[i].y, a[i].x, a[i].z);

			v[i] = 1;

		}

		if (!(k ^ (n - 1)))

			break;

	}

	de[1] = 1;

	dfs(1);

	aw X;

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

		if (!v[i])

		{

			X = lca(a[i].x, a[i].y);

			if (!(a[i].z^X.ma))

				mi = minn(mi, s - X.se_ma + a[i].z);

			else

				mi = minn(mi, s - X.ma + a[i].z);

		}

	printf("%lld", mi);

	return 0;

}

巴特西

BZOJ1977或洛谷4180 [BJWC2010]次小生成树

BZOJ原题链接

洛谷原题链接

最新文章

热门文章