Home » 国际竞赛 » Details

USACO 2022 US Open Contest, Silver Problem 1. Visits

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午6:42

USACO 2022 US Open Contest, Silver Problem 1. Visits

Each of Bessie’s $N$ ( $2 \leq N \leq 10^{5}$ ) bovine buddies (conveniently labeled $1 \dots N$ ) owns her own farm. For each $1 \leq i \leq N$ , buddy $i$ wants to visit buddy $a_{i}$ ( $a_{i} \neq i$ ).

Given a permutation $(p_{1}, p_{2}, \dots, p_{N})$ of $1 \dots N$ , the visits occur as follows.

For each $i$ from $1$ up to $N$ :

If buddy $a_{p_{i}}$ has already departed her farm, then buddy $p_{i}$ remains at her own farm.
Otherwise, buddy $p_{i}$ departs her farm to visit buddy $a_{p_{i}}$ ’s farm. This visit results in a joyful "moo" being uttered $v_{p_{i}}$ times ( $0 \leq v_{p_{i}} \leq 10^{9}$ ).

Compute the maximum possible number of moos after all visits, over all possible permutations $p$ .

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ .For each $1 \leq i \leq N$ , the $i + 1$ -st line contains two space-separated integers $a_{i}$ and $v_{i}$ .

OUTPUT FORMAT (print output to the terminal / stdout):

A single integer denoting the answer.Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

SAMPLE OUTPUT:

If $p = (1, 4, 3, 2)$ then

Buddy $1$ visits buddy $2$ 's farm, resulting in $10$ moos.
Buddy $4$ sees that buddy $1$ has already departed, so nothing happens.
Buddy $3$ visits buddy $4$ 's farm, adding $30$ moos.
Buddy $2$ sees that buddy $3$ has already departed, so nothing happens.

This gives a total of $10 + 30 = 40$ moos.

On the other hand, if $p = (2, 3, 4, 1)$ then

Buddy $2$ visits buddy $3$ 's farm, causing $20$ moos.
Buddy $3$ visits buddy $4$ 's farm, causing $30$ moos.
Buddy $4$ visits buddy $1$ 's farm, causing $40$ moos.
Buddy $1$ sees that buddy $2$ has already departed, so nothing happens.

This gives $20 + 30 + 40 = 90$ total moos. It can be shown that this is the maximum possible amount after all visits, over all permutations $p$ .

SCORING:

Test cases 2-3 satisfy $a_{i} \neq a_{j}$ for all $i \neq j$ .
Test cases 4-7 satisfy $N \leq 10^{3}$ .
Test cases 8-11 satisfy no additional constraints.

Problem credits: Benjamin Qi and Michael Cao

USACO 2022 US Open Contest, Silver Problem 1. Visits 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Observe that the edges $i \to a_{i}$ induce a directed graph where every vertex has out-degree 1. This is known as a functional graph. We can solve the problem for each connected component of the graph independently, so for the remainder of the analysis, we will assume the graph consists of a single connected component.

Call cow $i$ inactive if it contributes $0$ to the collective pleasure value rather than $v_{i}$ . From the sample case, among those cows on a simple cycle, it is easy to see that at least one of the cows must be inactive. Consider the cow $c$ in the cycle that occurs latest in $p$ . Then either $a_{c}$ either has not departed her farm already (in which case $a_{c}$ is inactive) or she has (in which case $c$ is inactive).

As a connected component in a functional graph always contains exactly one simple cycle, the answer must be at most the sum of all $v_{i}$ minus the minimum $v_{i}$ among that cycle. Furthermore, we can always construct $p$ that achieves this bound. The construction is as follows:

Let cow $c$ be the cow corresponding to the minimum $v_{i}$ along the cycle.
Any permutation $p$ such that $i$ appears earlier than $a_{i}$ in $p$ for all $i \neq c$ suffices.
After removing edge $c \to a_{c}$ from the component, the component no longer contains a cycle. Therefore, the remaining edges form a directed tree rooted at $c$ . So it is always possible to construct $p$ (ex. DFS backward through the tree and add each node to the front of $p$ when it's traversed for the first time).

In the code below, for each connected component I use Floyd's algorithm to detect a vertex along the cycle. After that, I mark every vertex in the connected component as visited. As each connected component is processed in time proportional to its size, the runtime is $O (N)$ .

#include <bits/stdc++.h>
using namespace std;

template <class T> using V = vector<T>;
#define all(x) begin(x), end(x)

vector<int> a, v;
vector<vector<int>> child;
vector<bool> done;

void mark_as_done(int x) {
	if (done[x]) return;
	done[x] = true;
	for (int c : child[x]) mark_as_done(c);
}

int solve(int start) {
	int x = start, y = start;
	do {
		x = a[x], y = a[a[y]];
	} while (x != y);
	int min_along_cycle = INT_MAX;
	do {
		min_along_cycle = min(min_along_cycle, v[x]);
		x = a[x];
	} while (x != y);
	mark_as_done(x);
	return min_along_cycle;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin >> N;
	a.resize(N + 1);
	v.resize(N + 1);
	child.resize(N + 1);
	int64_t ans = 0;
	for (int i = 1; i <= N; ++i) {
		cin >> a[i] >> v[i];
		ans += v[i];
		child[a[i]].push_back(i);
	}
	done.resize(N + 1);
	for (int i = 1; i <= N; ++i)
		if (!done[i]) ans -= solve(i);
	cout << ans << "\n";
}

Alternatively, if you are familiar with Gold topics, the answer is just the weight of a maximum spanning forest of the graph (treating the edges as undirected), which can be computed with Kruskal's algorithm.

#include <bits/stdc++.h>
using namespace std;

struct DSU {
	vector<int> e;
	void init(int N) { e = vector<int>(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return 1;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin >> N;
	vector<tuple<int, int, int>> edges;
	for (int i = 1; i <= N; ++i) {
		int a, v;
		cin >> a >> v;
		edges.push_back({v, i, a});
	}
	sort(edges.rbegin(), edges.rend());
	DSU D;
	D.init(N + 1);
	int64_t ans = 0;
	for (auto [v, x, y] : edges)
		if (D.unite(x, y)) ans += v;
	cout << ans << "\n";
}

Bonus: Solve the problem when the $v_{i}$ can be negative.

[/hide]