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]