BZOJ5289: [Hnoi2018]排列

传送门

第一步转化，令 \(q[p[i]]=i\)，那么题目变成：

有一些 \(q[a[i]]<q[i]\) 的限制，\(q\) 必须为排列，求 \(max(\sum_{i=1}^{n}w[i]q[i])\)

这个东西是可以建图的，\(i\rightarrow a[i]\)，不合法当且仅当有环

其它情况就是一棵树(\(0\) 为根)

也就是在这个树上依次选点，选 \(u\) 之前必须选择其父亲，第 \(i\) 次选的代价为 \(i\times w[u]\)。

考虑贪心，对于一个当前权值最小的点 \(u\) 来说，如果父亲是 \(0\)，那么肯定选它最优

否则，设父亲为 \(fa\)，那么选完 \(fa\) 之后一定会选 \(u\)，这样就可以合并这两个节点。

对于之后已经合并过的节点，设其权值和为 \(v[i]\)，大小为 \(c[i]\)

那么 \(i\) 先于 \(j\) 当且仅当

\(v[i]+c[i]\times v[j] \le v[j]+c[j]\times v[i]\)

也就是 \(i\) 的平均权值最小，以这个为关键字选最小的点就行了。

为了计算答案，把每个点的贡献在合并的时候拆开计算即可。

拿个 \(heap/segment\) + 并查集乱搞

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn(5e5 + 5);

int n, a[maxn], w[maxn], vis[maxn], in[maxn], fa[maxn], len;

ll ans;

struct Info {

	ll v;

	int id, cnt;

	inline int operator <(Info b) const {

		return v * b.cnt <= b.v * cnt;

	}

} mn[maxn << 2];

void Dfs(int u) {

	if (in[u]) puts("-1"), exit(0);

	if (vis[u]) return;

	vis[u] = 1, in[u] = 1;

	if (a[u]) Dfs(a[u]);

	in[u] = 0;

}

inline void Update(int p) {

    for (p >>= 1; p; p >>= 1) mn[p] = min(mn[p << 1], mn[p << 1 | 1]);

}

inline void Modify(int p, Info v) {

    p += len - 1, mn[p] = v, Update(p);

}

inline int Find(int x) {

	return (fa[x] ^ x) ? fa[x] = Find(fa[x]) : x;

}

int main() {

	int i, p, c, ff, cnt = 1;

	ll v;

	scanf("%d", &n);

	for (i = 1; i <= n; ++i) scanf("%d", &a[i]), fa[i] = i;

	for (i = 1; i <= n; ++i) scanf("%d", &w[i]);

	for (i = 1; i <= n; ++i) if (!vis[i]) Dfs(i);

	for (len = 1; len < n; len <<= 1);

	for (i = len << 1; i; --i) mn[i] = (Info){(ll)2e13, 0, 0};

	for (i = 1; i <= n; ++i) mn[i + len - 1] = (Info){w[i], i, 1};

	for (i = len - 1; i; --i) mn[i] = min(mn[i << 1], mn[i << 1 | 1]);

	while (true) {

		p = mn[1].id, c = mn[1].cnt, v = mn[1].v;

		if (!p) break;

		Modify(p, (Info){(ll)2e13, 0, 0});

		if (!(ff = Find(a[p]))) {

			fa[p] = 0, ans += v * cnt, cnt += c;

			continue;

		}

		fa[p] = ff, ans += v * mn[ff + len - 1].cnt;

		mn[ff + len - 1].v += v, mn[ff + len - 1].cnt += c;

		Update(ff + len - 1);

	}

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

	return 0;

}

巴特西

BZOJ5289: [Hnoi2018]排列

最新文章

热门文章