「PA2014」Fiolki

传送门

Bzoj

解题思路

构造法。

对于每一次的倾倒操作，连边 \(newnode\to u,newnode\to v\)。

最后所有的反应都会在构造出来的树上的对应两点的 \(\text{LCA}\) 处发生。

把所有的反应按照 \(\text{LCA}\) 深度排序，深度相同则按输入顺序排序，模拟一下就好了。

记得用并查集判连通性，还有树剖LCA跑得比倍增LCA快多了。

细节注意事项

咕咕咕。

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= (c == '-'), c = getchar();

	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

	s = f ? -s : s;

}

const int _ = 400002;

const int __ = 500002;

int tot, head[_], nxt[_], ver[_];

inline void Add_edge(int u, int v)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }

int n, m, k, tt, g[_], Fa[_];

int fa[_], dep[_], siz[_], son[_], top[_];

struct node { int c, d, lca, id; } t[__];

inline bool cmp(const node& x, const node& y)

{ return dep[x.lca] == dep[y.lca] ? x.id < y.id : dep[x.lca] > dep[y.lca]; }

inline int findd(int x) { return Fa[x] == x ? x : Fa[x] = findd(Fa[x]); }

inline void dfs1(int u, int f) {

	siz[u] = 1, dep[u] = dep[f] + 1, fa[u] = f;

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i];

		dfs1(v, u), siz[u] += siz[v];

		if (siz[v] > siz[son[u]]) son[u] = v;

	}

}

inline void dfs2(int u, int topf) {

	top[u] = topf;

	if (!son[u]) return ; dfs2(son[u], topf);

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i]; if (v == son[u]) continue;

		dfs2(v, v);

	}

}

inline int LCA(int x, int y) {

	int fx = top[x], fy = top[y];

	while (fx != fy) {

		if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);

		x = fa[fx], fx = top[x];

	}

	return dep[x] < dep[y] ? x : y;

}

int main() {

	read(n), read(m), read(k), tt = n;

	for (rg int i = 1; i <= n; ++i) read(g[i]);

	for (rg int i = 1; i <= n + m; ++i) Fa[i] = i;

	for (rg int u, v, i = 1; i <= m; ++i) {

		read(u), u = findd(u);

		read(v), v = findd(v);

		Fa[u] = Fa[v] = ++tt;

		Add_edge(tt, u), Add_edge(tt, v);

	}

	for (rg int i = 1; i <= tt; ++i)

		if (findd(i) == i) dfs1(i, 0), dfs2(i, i);

	for (rg int c, d, i = 1; i <= k; ++i)

		read(c), read(d), t[i] = (node) { c, d, LCA(c, d), i };

	sort(t + 1, t + k + 1, cmp);

	long long ans = 0;

	for (rg int u, v, i = 1; i <= k; ++i) {

		if (findd(u = t[i].c) != findd(v = t[i].d)) continue;

		int tmp = min(g[u], g[v]);

		ans += 2ll * tmp, g[u] -= tmp, g[v] -= tmp;

	}

	printf("%lld\n", ans);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「PA2014」Fiolki

解题思路

细节注意事项

参考代码

最新文章

热门文章