test/graph/topological_sort.get.test.cpp

• View this file on GitHub
• Last update: 2025-11-15 20:52:05+09:00
• Problem: https://yukicoder.me/problems/no/468

Depends on

• Topological Sort (トポロジカルソート) (graph/topological_sort.hpp)
• template/constant.hpp
• template/include.hpp
• template/macro.hpp
• 提出用テンプレート (template/template.hpp)
• template/type_alias.hpp
• Choose Minimum / Maximum (utility/choose_min_max.hpp)
• utility/set_io.hpp

Required by

• test/utility/next_combination.test.cpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/468"

#include "../../graph/topological_sort.hpp"
#include "../../template/template.hpp"

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<pair<int, int>>> g(N);
    TopologicalSort ts(N);
    TopologicalSort ts_inv(N);

    rep (i, 0, M) {
        int u, v, w;
        cin >> u >> v >> w;

        g[u].emplace_back(v, w);
        ts.add_edge(u, v);
        ts_inv.add_edge(v, u);
    }

    ts.build();
    ts_inv.build();

    assert(ts.is_dag());
    assert(ts_inv.is_dag());

    vector<int> dp(N, 0);
    vector<int> ep(N, INF<int>);
    ep[0] = 0;

    rep (i, 0, N) {
        int v = ts.get(i);
        for (auto [nv, co] : g[v]) {
            dp[nv] = max(dp[nv], dp[v] + co);
        }
    }

    ep[N - 1] = dp[N - 1];

    rep (i, 0, N) {
        int v = ts_inv.get(i);
        for (auto [nv, co] : g[v]) {
            ep[v] = min(ep[v], ep[nv] - co);
        }
    }

    int cnt = N;
    rep (i, 0, N) {
        if (dp[i] == ep[i]) {
            cnt--;
        }
    }

    cout << dp[N - 1] << ' ' << cnt << '/' << N << LF;

    return 0;
}

#line 1 "test/graph/topological_sort.get.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/468"

#line 2 "graph/topological_sort.hpp"

#line 2 "template/template.hpp"

/**
 * @author ku_senjan
 * @title 提出用テンプレート
 * @see https://github.com/kogetsu0728/ku-library
 */

#line 2 "template/constant.hpp"

#line 2 "template/include.hpp"

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
using namespace std;
#line 2 "template/type_alias.hpp"

#line 4 "template/type_alias.hpp"

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

using ld = long double;

template <class T, bool REVERSE = false>
using heap = priority_queue<T, vector<T>, conditional_t<REVERSE, greater<T>, less<T>>>;
#line 5 "template/constant.hpp"

template <class T>
inline constexpr T INF = numeric_limits<T>::max() / 2;

inline constexpr array<int, 4> DY4 = {0, -1, 0, 1};
inline constexpr array<int, 4> DX4 = {1, 0, -1, 0};
inline constexpr array<int, 8> DY8 = {0, -1, -1, -1, 0, 1, 1, 1};
inline constexpr array<int, 8> DX8 = {1, 1, 0, -1, -1, -1, 0, 1};

inline constexpr char LF = '\n';
#line 2 "template/macro.hpp"

#line 5 "template/macro.hpp"

/**
 * @see https://trap.jp/post/1224/
 */

#ifdef LOCAL
inline constexpr bool IS_LOCAL = true;
#else
inline constexpr bool IS_LOCAL = false;
#endif

#define IF_LOCAL if constexpr (IS_LOCAL)

#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)

#define overload4(a, b, c, d, e, ...) e

#define rep1(i, a) for (ll i = 0; (i) < (ll)(a); ++(i))
#define rep2(i, a, b) for (ll i = (ll)(a); (i) < (ll)(b); ++(i))
#define rep3(i, a, b, c) for (ll i = (ll)(a); (i) < (ll)(b); (i) += (ll)(c))
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)

#define rrep1(i, a) for (ll i = (ll)(a); (i) >= 0; --(i))
#define rrep2(i, a, b) for (ll i = (ll)(a); (i) >= (ll)(b); --(i))
#define rrep3(i, a, b, c) for (ll i = (ll)(a); (i) >= (ll)(b); (i) -= (ll)(c))
#define rrep(...) overload4(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#line 13 "template/template.hpp"

#line 2 "utility/choose_min_max.hpp"

/**
 * @title Choose Minimum / Maximum
 */

template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }

    return false;
}

template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }

    return false;
}
#line 2 "utility/set_io.hpp"

#line 4 "utility/set_io.hpp"

void set_io(int d = 16) {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(d);

    return;
}
#line 4 "graph/topological_sort.hpp"

/**
 * @brief Topological Sort (トポロジカルソート)
 * @note 参考: https://algo-logic.info/topological-sort/
 */
class TopologicalSort {
  private:
    bool init, dag;
    int n;
    vector<vector<int>> g;
    vector<int> p;

  public:
    TopologicalSort() : TopologicalSort(0) {}
    TopologicalSort(int _n) : init(false), dag(false), n(_n), g(_n), p(0) {}

    void add_edge(int u, int v) noexcept {
        assert(!init);

        g[u].emplace_back(v);
    }

    void build() noexcept {
        assert(!init);
        init = true;

        vector<int> cnt(n);
        rep (v, 0, n) {
            for (int nv : g[v]) {
                cnt[nv]++;
            }
        }

        queue<int> que;
        rep (v, 0, n) {
            if (cnt[v] == 0) {
                que.emplace(v);
            }
        }

        p.reserve(n);
        while (!que.empty()) {
            int v = que.front();
            que.pop();

            p.emplace_back(v);

            for (int nv : g[v]) {
                cnt[nv]--;

                if (cnt[nv] == 0) {
                    que.emplace(nv);
                }
            }
        }

        if (int(p.size()) == n) {
            dag = true;
        } else {
            p.clear();
        }

        return;
    }

    bool is_dag() const {
        assert(init);

        return dag;
    }

    int get(int i) const {
        assert(init);
        assert(dag);

        return p[i];
    }
};
#line 5 "test/graph/topological_sort.get.test.cpp"

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<pair<int, int>>> g(N);
    TopologicalSort ts(N);
    TopologicalSort ts_inv(N);

    rep (i, 0, M) {
        int u, v, w;
        cin >> u >> v >> w;

        g[u].emplace_back(v, w);
        ts.add_edge(u, v);
        ts_inv.add_edge(v, u);
    }

    ts.build();
    ts_inv.build();

    assert(ts.is_dag());
    assert(ts_inv.is_dag());

    vector<int> dp(N, 0);
    vector<int> ep(N, INF<int>);
    ep[0] = 0;

    rep (i, 0, N) {
        int v = ts.get(i);
        for (auto [nv, co] : g[v]) {
            dp[nv] = max(dp[nv], dp[v] + co);
        }
    }

    ep[N - 1] = dp[N - 1];

    rep (i, 0, N) {
        int v = ts_inv.get(i);
        for (auto [nv, co] : g[v]) {
            ep[v] = min(ep[v], ep[nv] - co);
        }
    }

    int cnt = N;
    rep (i, 0, N) {
        if (dp[i] == ep[i]) {
            cnt--;
        }
    }

    cout << dp[N - 1] << ' ' << cnt << '/' << N << LF;

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	manual1.txt	AC	5 ms	3 MB
g++	manual2.txt	AC	4 ms	4 MB
g++	manual3.txt	AC	4 ms	4 MB
g++	sample00_small.txt	AC	4 ms	3 MB
g++	sample01.txt	AC	4 ms	4 MB
g++	sample01_small.txt	AC	4 ms	4 MB
g++	sample02_small.txt	AC	4 ms	4 MB
g++	sample03_small.txt	AC	4 ms	3 MB
g++	sample04_small.txt	AC	4 ms	4 MB
g++	sample05_small.txt	AC	4 ms	3 MB
g++	sample06_small.txt	AC	4 ms	3 MB
g++	sample07_small.txt	AC	4 ms	4 MB
g++	sample08_small.txt	AC	5 ms	4 MB
g++	sample09_small.txt	AC	4 ms	4 MB
g++	sample10_mid.txt	AC	6 ms	4 MB
g++	sample11_mid.txt	AC	6 ms	4 MB
g++	sample12_mid.txt	AC	6 ms	4 MB
g++	sample13_mid.txt	AC	6 ms	4 MB
g++	sample14_mid.txt	AC	6 ms	4 MB
g++	sample15_mid.txt	AC	6 ms	4 MB
g++	sample16_mid.txt	AC	6 ms	4 MB
g++	sample17_mid.txt	AC	6 ms	4 MB
g++	sample18_mid.txt	AC	6 ms	4 MB
g++	sample19_mid.txt	AC	6 ms	4 MB
g++	sample20_large_1.txt	AC	210 ms	23 MB
g++	sample21_large1.txt	AC	211 ms	23 MB
g++	sample22_large_1.txt	AC	209 ms	23 MB
g++	sample23_large_1.txt	AC	210 ms	23 MB
g++	sample24_large1.txt	AC	209 ms	23 MB
g++	sample25_large1.txt	AC	212 ms	23 MB
g++	sample26_large1.txt	AC	210 ms	23 MB
g++	sample27_large1.txt	AC	209 ms	23 MB
g++	sample28_large1.txt	AC	209 ms	23 MB
g++	sample29_large1.txt	AC	211 ms	23 MB
g++	straight_large1.txt	AC	74 ms	21 MB
g++	straight_mid.txt	AC	6 ms	4 MB
g++	straight_small.txt	AC	5 ms	4 MB

Back to top page