mayoko’s diary

プロコンとかいろいろ。

第2回早稲田大学プログラミングコンテスト E - 独立記念日

解法はすぐわかったけどめっちゃバグらせまくりました…

解法

閉路がない場合を考えます。

この場合は, 辺を一本切るごとに独立したグループが一つ増えるので, コストが小さい順に貪欲に辺を切っていって大丈夫です。

閉路がある場合は, 2 通りの場合が生じます。

閉路から何本か辺を切る場合
この場合は, 上と同じように考えればいけます。

閉路から一本も辺を切らない場合
閉路を一つのまとまった頂点と見ると, (サイクル長が C として)頂点が N-C+1 個あることになります。このグラフについて, 上と同じように貪欲に辺を切っていけば良いです。

問題を解く前提に, 閉路検出がありますが, これは以前にやりました。
mayokoex.hatenablog.com

struct Edge {
    int u;
    int v;
    int cost;
    Edge() {}
    Edge(int u, int v, int cost) : u(u), v(v), cost(cost) {}
    bool operator<(const Edge& rhs) const {return cost < rhs.cost;}
};

ll calc(vector<Edge> es, int N, int K) {
    sort(es.begin(), es.end());
    int M = es.size();
    ll ret = 0;
    int need = max(0, M-(N-K));
    for (int i = 0; i < need; i++) ret += es[i].cost;
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, K;
    cin >> N >> M >> K;
    vector<Edge> es(M);
    vector<vector<Edge>> G(N);
    vector<int> degree(N);
    for (int i = 0; i < M; i++) {
        cin >> es[i].u >> es[i].v >> es[i].cost;
        es[i].u--; es[i].v--;
        G[es[i].u].push_back(es[i]);
        G[es[i].v].push_back(es[i]);
        degree[es[i].u]++;
        degree[es[i].v]++;
    }
    queue<int> que;
    for (int i = 0; i < N; i++) {
        if (degree[i] == 1) {
            que.push(i);
            degree[i] = 0;
        }
    }
    while (!que.empty()) {
        int now = que.front(); que.pop();
        for (Edge e : G[now]) {
            int ch = (e.u == now ? e.v : e.u);
            if (degree[ch] == 0) continue;
            if (--degree[ch] == 1) {
                degree[ch] = 0;
                que.push(ch);
            }
        }
    }
    vector<int> cycle;
    for (int i = 0; i < M; i++) {
        Edge e = es[i];
        if (degree[e.u] > 0 && degree[e.v] > 0) {
            cycle.push_back(i);
        }
    }
    ll ans = 1ll<<55;
    if (cycle.empty()) {
        ans = calc(es, N, K);
    } else {
        for (int c : cycle) {
            vector<Edge> tmp;
            for (int i = 0; i < M; i++) if (i != c) {
                tmp.push_back(es[i]);
            }
            ans = min(ans, es[c].cost + calc(tmp, N, K));
        }
        int C = cycle.size();
        if (N-C+1 >= K) {
            vector<Edge> tmp;
            for (int i = 0; i < M; i++) if (find(cycle.begin(), cycle.end(), i) == cycle.end()) {
                tmp.push_back(es[i]);
            }
            sort(tmp.begin(), tmp.end());
            ll unko = 0;
            // 消す本数
            int need = max(0, M-C - (N-C-K+1));
            for (int i = 0; i < need; i++) unko += tmp[i].cost;
            ans = min(ans, unko);
        }
    }
    cout << ans << endl;
    return 0;
}