USACO 2022 US Open Contest, Silver Problem 1. Visits

USACO 2022 US Open Contest, Silver Problem 1. Visits

Each of Bessie’s NN (2N1052≤N≤105) bovine buddies (conveniently labeled 1N1…N) owns her own farm. For each 1iN1≤i≤N, buddy ii wants to visit buddy aiai (aiiai≠i).

Given a permutation (p1,p2,,pN)(p1,p2,…,pN) of 1N1…N, the visits occur as follows.

For each ii from 11 up to NN:

 

  • If buddy apiapi has already departed her farm, then buddy pipi remains at her own farm.
  • Otherwise, buddy pipi departs her farm to visit buddy apiapi’s farm. This visit results in a joyful "moo" being uttered vpivpi times (0vpi1090≤vpi≤109).

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

 

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

The first line contains NN.For each 1iN1≤i≤N, the i+1i+1-st line contains two space-separated integers aiai and vivi.

 

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:

4
2 10
3 20
4 30
1 40

SAMPLE OUTPUT:

90

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

 

  • Buddy 11 visits buddy 22's farm, resulting in 1010 moos.
  • Buddy 44 sees that buddy 11 has already departed, so nothing happens.
  • Buddy 33 visits buddy 44's farm, adding 3030 moos.
  • Buddy 22 sees that buddy 33 has already departed, so nothing happens.

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

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

 

  • Buddy 22 visits buddy 33's farm, causing 2020 moos.
  • Buddy 33 visits buddy 44's farm, causing 3030 moos.
  • Buddy 44 visits buddy 11's farm, causing 4040 moos.
  • Buddy 11 sees that buddy 22 has already departed, so nothing happens.

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

SCORING:

  • Test cases 2-3 satisfy aiajai≠aj for all iji≠j.
  • Test cases 4-7 satisfy N103N≤103.
  • 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 iaii→ai 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 ii inactive if it contributes 00 to the collective pleasure value rather than vivi. 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 cc in the cycle that occurs latest in pp. Then either acac either has not departed her farm already (in which case acac is inactive) or she has (in which case cc 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 vivi minus the minimum vivi among that cycle. Furthermore, we can always construct pp that achieves this bound. The construction is as follows:

 

  1. Let cow cc be the cow corresponding to the minimum vivi along the cycle.
  2. Any permutation pp such that ii appears earlier than aiai in pp for all ici≠c suffices.
  3. After removing edge cacc→ac from the component, the component no longer contains a cycle. Therefore, the remaining edges form a directed tree rooted at cc. So it is always possible to construct pp (ex. DFS backward through the tree and add each node to the front of pp 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)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 vivi can be negative.

[/hide]

翰林国际教育资讯二维码