USACO 2022 US Open Contest Silver Division - Visits

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Create a directed graph, and each node only has one edge going out. Whever there is a cycle, you can include all but one edge, so whenever you see a cycle, find the smallest value of all the edges in the cycle and remove that from the total sum of edges.

Source code

The source code in C++ can be seen below.

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> v(n);

    vector<pair<int, int>> g(n);

    long long total_weight = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i] >> v[i];
        a[i]--;
        g[i] = {a[i], v[i]};
        total_weight += v[i];
    }

    vector<bool> visited(n);
    long long total_weight_removed = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            vector<int> nodes;
            nodes.push_back(i);
            visited[i] = true;
            int buddy = g[i].first;

            while (!visited[buddy]) {
                nodes.push_back(buddy);
                visited[buddy] = true;
                buddy = g[buddy].first;
            }

            bool cycle = false;
            int smallest = 1e9;
            for (int i = 0; i < nodes.size(); i++) {
                if (nodes[i] == buddy) {
                    cycle = true;
                }
                if (cycle) {
                    smallest = min(smallest, g[nodes[i]].second);
                }
            }
            if (cycle) total_weight_removed += smallest;
        }
    }
    cout << total_weight - total_weight_removed << '\n';
}