USACO

USACO 5.4 Canada Tour

For every pair of cities (i,j) find maximum total length of two paths. One path starts at city 1 and ends in city i, the other path starts from city 1 and ends in city j. Both path have no common cities except the start city 1 and the end city N. First path will reach city N, and the result will be the maximum value of the other path ending at j where 1 <= j <= N.

#include <vector>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <string>

using namespace std;

int N, V;
vector<vector<int>> dp;
vector<vector<bool>> flight;
unordered_map<string, int> cities;

int main() {
    ifstream fin("tour.in");
    ofstream fout("tour.out");

    fin >> N >> V;
    dp = vector<vector<int>>(N + 1, vector<int>(N + 1));
    flight = vector<vector<bool>>(N + 1, vector<bool>(N + 1, false));
    
    string city;
    for (int i = 1; i <= N; ++i) {
        fin >> city;
        cities[city] = i;
    }
    
    string from, to;
    for (int i = 0; i < V; ++i) {
        fin >> from >> to;
        flight[cities[from]][cities[to]] = true;
        flight[cities[to]][cities[from]] = true;
    }
    
    dp[1][1] = 1;
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            for (int k = 1; k < j; ++k) {
                if (dp[i][k] && flight[k][j]) {
                    dp[i][j] = std::max(dp[i][k] + 1, dp[i][j]);
                }
                dp[j][i] = dp[i][j];
            }
        }
    }
    
    int ans = 1;
    for (int i = 1; i <= N; ++i) {
        if (!flight[i][N]) continue;
        ans = std::max(ans, dp[i][N]);
    }
    
    cout << ans << endl;
    fout << ans << endl;
}

USACO

USACO 5.3 Big Barn

Similar dynamic programming problem as the previous Home On The Range.


#include <vector>
#include <iostream>
#include <fstream>
#include <climits>

using namespace std;
int N, T;
vector<vector<int>> dp;

int main() {
    ifstream fin("bigbrn.in");
    ofstream fout("bigbrn.out");
    
    fin >> N >> T;
    dp = vector<vector<int>>(N, vector<int>(N, 1));
    int x, y;
    for (int i = 0; i < T; ++i) {
        fin >> x >> y;
        dp[x - 1][y - 1] = 0;
    }
    
    int ans = INT_MIN;
    for (int i = N - 2; i >= 0; --i) {
        for (int j = N - 2; j >= 0; --j) {
            if (!dp[i][j]) continue;
            dp[i][j] = std::min(std::min(dp[i + 1][j], dp[i][j + 1]),
                                dp[i + 1][j + 1]) + 1;
            ans = std::max(dp[i][j], ans);
        }
    }
    
    cout << ans << endl;
    fout << ans << endl;
}

USACO

USACO 5.3 Network of Schools

Compute the minimum number of edges to add to make a directed graph strongly connected. Use Kosaraju’s algorithm to find out strongly connected components and for each SCC count its in degree and out degree and the maximum one is the answer.


#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int N;
vector<vector<int>> g, rg /* reversed graph */;
vector<int> vs; // post order vertices
vector<bool> visited;
vector<int> cmp; // topological order of strongly connected component.

void add_edge(int from, int to) {
    g[from].push_back(to);
    rg[to].push_back(from);
}

void dfs(int v) {
    visited[v] = true;
    for (int i = 0; i < g[v].size(); ++i) {
        if (visited[g[v][i]]) continue;
        dfs(g[v][i]);
    }
    vs.push_back(v);
}

void rdfs(int v, int k) {
    visited[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rg[v].size(); ++i) {
        if (visited[rg[v][i]]) continue;
        rdfs(rg[v][i], k);
    }
}

int scc() {
    std::fill(visited.begin(), visited.end(), false);
    vs.clear();
    for (int i = 0; i < N; ++i) {
        if (visited[i]) continue;
        dfs(i);
    }
    std::fill(visited.begin(), visited.end(), false);
    int k = 0;
    for (int i = (int)vs.size() - 1; i >= 0; --i) {
        if (visited[vs[i]]) continue;
        rdfs(vs[i], k++);
    }
    return k;
}

int main() {
    ifstream fin("schlnet.in");
    ofstream fout("schlnet.out");
    
    fin >> N;
    g = vector<vector<int>>(N); rg = g;
    vs = vector<int>(N);
    visited = vector<bool>(N, false);
    cmp = vector<int>(N, 0);
    auto ins = vector<int>(N, 0);
    auto outs = vector<int>(N, 0);
    
    for (int i = 0; i < N; ++i) {
        int t; fin >> t;
        while (t) {
            add_edge(i, t - 1);
            fin >> t;
        }
    }
    
    int numOfScc = scc();
    
    //cout << numOfScc << endl;
    
    if(numOfScc == 1)
    {
        cout << 1 << endl << 0 << endl;
        fout << 1 << endl << 0 << endl;

        return 0;
    }
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < g[i].size(); ++j) {
            int v = g[i][j];
            int ii = cmp[i], vv = cmp[v];
            if(ii != vv) {
                ins[vv]++; outs[ii]++;
            }
        }
    }
    
    int ans0 = 0, ans1 = 0;
    for(int i = 0; i < numOfScc; ++i) {
        if(!ins[i])  ++ans0; if(!outs[i]) ++ans1;
    }
    cout << ans0 << endl << max(ans0, ans1) << endl;
    fout << ans0 << endl << max(ans0, ans1) << endl;
    return 0;
}