A - グラフ / Graph

https://atcoder.jp/contests/cf16-tournament-round1-open/tasks/asaporo_c

解法

最小全域木で使わない辺は使わないため、候補を4000本まで減らせる（300点）　　

ここで問題はstがコスト0で繋がっているとみなせるため、最小全域木のst間の最も重い辺を削除でき、これが答え

事前に、最小全域木に対して任意の二点間のパスに含まれる最大の辺のコストを求めておけば解ける

https://atcoder.jp/contests/cf16-tournament-round1-open/submissions/4681698

void solve() {
    cin >> n >> m;
    digraph<> g(2 * k5);
    rep(i, m) {
        int f, t, c;
        cin >> f >> t >> c;
        --f, --t;
        g.add(f, t, c);
    }
    sort(g.edges);
    UnionFind uf(k5);
    undigraph<> sg(4040);
    fora(e, g.edges) {
        if (uf.same(e.f, e.t))con;
        uf.unite(e.f, e.t);
        sg.add(e.f, e.t, e.c);
        cou += e.c;
    }

    vvi(emi, 4040, 4040);
    function<void(int, int, int, int)> ds = [&](int s, int i, int p, int ma) {
        emi[s][i] = ma;
        fort(gi, sg[i]) {
            ds(s, t, i, max(ma, c));
        }
    };
    rep(i, n){
        ds(i, i, -1, -0);
    }

    cin >> q;
    while (q--) {
        int s,t;
        cin>>s>>t;
        --s,--t;
        cout << cou - emi[s][t] << endl;
    }

}