The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

Problem link
The reading experience is better on the blog

1: Brief Problem Statement

There are $N$ cows. Cow $i (1 \le N)$ wants to visit cow $a_i (a_i \ne i)$ . If $a_i$ has already left to visit another cow, then $i$ cannot successfully visit $a_i$ ; otherwise, this successful visit can produce $v_i$ moos. Find the maximum possible number of moos.

2: Analysis

After understanding the problem, we can first analyze the sample and try to find some useful information.

To make the sample easier to analyze, we can display it as a graph. Two nodes connected by a directed edge represent a cow and the cow it wants to visit ( $i$ and $a_i$ ). The edge weight is the number of moos that this visit can produce.

From this graph, we can see that, regardless of the visiting order, at most three visits can succeed. The final visit must encounter a cow that has already been encountered. Therefore, choosing $2 \rarr 3$ , $3 \rarr 4$ , and $4 \rarr 1$ achieves the maximum number of moos, namely $20 + 30 + 40 = 90$ .

Thinking more carefully about this sample, we can see that the essential reason why all four edges cannot be selected simultaneously is that doing so produces a cycle in the graph. If the graph contains a cycle and every edge on the cycle must be traversed, then we will inevitably visit a node that has already been visited.

If we can select some edges from the original graph to construct a graph without cycles, then we can certainly find a visiting order in which no node is visited repeatedly while traversing all nodes. Without forming a cycle, we also need to select edges with large weights as much as possible. This satisfies the problem’s requirement: producing the maximum number of moos.

A cycle-free graph with the greatest weight? This seems very similar to a minimum (maximum) spanning tree.

After analyzing this far, it is relatively easy to think of using a minimum (maximum) spanning-tree algorithm. Such an algorithm allows us to find the tree with the greatest weight in a graph. However, this is still not exactly the same as this problem. We also need to resolve the following issue:

Minimum (maximum) spanning-tree algorithms can only be used on undirected graphs, while our current graph is directed. Can we therefore use a minimum (maximum) spanning-tree algorithm directly on this problem?

(If you understand this part, you can go directly to the code.) The code is standard Kruskal.

Another way to state the question is: is the undirected graph converted from the directed graph equivalent to the original graph?

In the situation shown above, all three edges can be selected regardless of the visiting order. After converting it to an undirected graph, however, only two edges can be selected (selecting three edges creates a cycle).

In the problem, every cow has only one cow that it wants to visit. In other words, every node in the graph has an out-degree of $1$ . Under this condition, the situation in the figure above cannot occur (node $1$ in the figure has an out-degree of $2$ ), and the converted undirected graph is equivalent to the original graph.

Then why does only an in-degree greater than $1$ cause the converted undirected graph not to be equivalent to the original directed graph?

We know that if there are $n$ nodes, the minimum number of edges needed to include these $n$ nodes in a cycle is $n$ . Moreover, the out-degree and in-degree of every node among these $n$ nodes are both equal to $1$ , just as in the sample.

One edge can produce one out-degree and one in-degree. Therefore, the cycle has a total degree of $2n$ . If we allow some nodes to have an out-degree greater than $1$ , then the in-degree of some nodes may become $0$ (the sum of the degrees must be $20$ ; if the out-degree increases, the in-degree must decrease). In this way, when the in-degree is $0$ , no other node can reach that node, so a cycle naturally cannot be formed.

However, if it is directly converted into an undirected graph, the sum of the out-degrees and in-degrees is still $2n$ , and the degree of every node is also $2$ , so a cycle can be formed.

Thus, a problem arises during conversion.

3: Code

Here I used Kruskal to find the maximum spanning tree. Compared with the reasoning required by this problem, the code is relatively simple; only the sorting order from the minimum-spanning-tree algorithm needs to be changed.

If you are unfamiliar with minimum-spanning-tree algorithms, you can refer to the solutions for this template problem.

Note that the sum of the weights may exceed the range of int, so long long is required.

/*Date: 22 - 03-26 15 28
PROBLEM_NUM: USACO MAR Problem 1. Visits*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
#define ll long long
struct E
{
    int from, to, val;
} e[MAXN];
int n;
int fa[MAXN];
int find_fa(int cur)
{
    if (cur == fa[cur])
        return cur;
    return fa[cur] = find_fa(fa[cur]);
}
void merge(int a, int b)
{
    int af = find_fa(a), bf = find_fa(b);
    fa[af] = bf;
}
// Disjoint-set operations.

ll ans;

int main()
{
    scanf("%d", &n);
    iota(fa + 1, fa + 1 + n, 1);// Initially, fa[i] = i.
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &e[i].to, &e[i].val);
        e[i].from = i;
    }
    sort(e + 1, e + 1 + n, [](E a, E b)
         { return a.val > b.val; });// Put edges with larger weights first.
    int used_edge = 0;
    for (int i = 1; i <= n; i++)// Kruskal.
    {
        if (find_fa(e[i].from) != find_fa(e[i].to))
        {
            used_edge++;
            ans += e[i].val;
            merge(e[i].from, e[i].to);
            if (used_edge == n - 1)
            {
                break;
            }
        }
    }
    printf("%lld\n", ans);
    system("pause");
}

Finally, I hope this solution can help you. If there is anything you do not understand, or if you find a problem with the solution, you are welcome to contact me through the comments or a private message.