Andrew and Taxi [Codeforces Round #532 (Div. 2) E]

https://codeforces.com/contest/1100/problem/E

N頂点、M辺の有向グラフがある。
辺には有向辺の向きを変えるのに必要なコストCがある。
任意本の辺の向きを変えて有向グラフをDAGにしたい（サイクルを無くしたい）。
必要なコストの最小値と、その時向きを変える必要のある辺を答えよ。

注意
・必要なコストは向きを変える辺のコストの最大値（総和じゃない）
・向きを変える必要のある辺の本数は最小化する必要はない

N,M≦10^5

前提知識

• トポロジカルソート

解説

https://codeforces.com/contest/1100/submission/48351985

まずは、必要なコストの最小値を求めよう。
これは二分探索で求められる。
check(c) := コストcを使ってDAGを作れるか
コストcを使うことで、コストがc以下の辺の向きを自由に変えられる。
よって、この辺については融通がきくので、逆にコストがcより大きい辺だけでサイクルが存在しないようにすればいい。
よって、check関数では閉路判定をすることになる。
自分はこの閉路判定をトポロジカルソートの計算過程を使って行った。
（別になんでもいいんだが、あとでトポロジカルソートを使う関係でついでに使った感じ）
　
どちらかというと後半の方が大変で、向きを変えるかどうかを考えていこう。
solve(x) := コストxを使って、DAGを作るときに向きを変える必要のある辺の集合
方針としては、全ての頂点に適切に深さを定めて、深さが深い所から浅い所への辺は反転させることにする。
よって、「全ての頂点に適切に深さを定める」という所がキモなのだが、ここでトポロジカルソートを使う。
まずは、根の頂点を用意して、根の頂点から全ての頂点に辺を貼る。
そして、DAGが作れる辺。コストがxより大きい辺だけを貼る。
これでトポロジカルソートして、その順で深さを決めていく。
根の頂点の深さをdpt[root]=1として、子供にdpt[root]+1を伝搬させていく。
複数の親から深さを貰う場合は、最大値を使うことで親子関係と深さの関係を正しく保つことができる。
あとは、深さを見て、反転させるかを入れていく。
注意すべきこととして、深さが同じ場合はタイブレークをして、遷移を頂点の大きい方から小さい方にすればいい（どっちからどっちでもいい。適当にコードを書いたらこうなっただけ）。

int N, M;
vector<pair<int, int>> E[101010];
int A[101010], B[101010], C[101010];
//---------------------------------------------------------------------------------------------------
int check(int c) {
    TopologicalSort ts(N);
    rep(i, 0, M) if (c < C[i]) ts.add_edge(A[i], B[i]);
    vector<int> ord;
    return ts.sort(ord);
}
//---------------------------------------------------------------------------------------------------
int dpt[101010];
vector<int> solve(int x) {
    TopologicalSort ts(N + 1);
    rep(i, 0, N) ts.add_edge(N, i);
    rep(i, 0, M) if (x < C[i]) ts.add_edge(A[i], B[i]);
    vector<int> ord;
    ts.sort(ord);

    rep(_, 0, N + 1) {
        int cu = ord[_];
        
        if (cu == N) dpt[cu] = 1;
        fore(p, E[cu]) {
            int to = p.first;
            int i = p.second;

            if (x < C[i]) chmax(dpt[to], dpt[cu] + 1);
        }
    }

    vector<int> res;
    rep(i, 0, M) {
        int a = A[i];
        int b = B[i];
        if (dpt[a] > dpt[b]) res.push_back(i);
        else if (dpt[a] == dpt[b] and a < b) res.push_back(i);
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        E[a].push_back({ b, i });

        A[i] = a, B[i] = b, C[i] = c;
    }

    //rep(i, 1, N + 1) printf("%d %d\n", i, check(i));

    int ng = -1, ok = inf;
    while (ng + 1 != ok) {
        int md = (ok + ng) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }

    int ans1 = ok;
    auto ans2 = solve(ok);
    int n = ans2.size();

    printf("%d %d\n", ans1, n);
    rep(i, 0, n) {
        if (i) printf(" ");
        printf("%d", ans2[i] + 1);
    }
    printf("\n");
}