Submission #61685

---

Source Code Expand

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int kInf = (1 << 30) - 1;

struct Edge
{
    int u, v, cost;

    bool operator<(const Edge& other) const
    {
        return cost < other.cost;
    }
};

template <typename Set, typename T>
bool contains(const Set& c, const T& value)
{
    return c.find(value) != c.end();
}

bool find_cycle(const vector<Edge>& e, int k, int k0, set<int>* cycle)
{
    if (cycle->find(k) != cycle->end()) {
        return true;
    }

    cycle->insert(k);
    for (size_t i = 0; i < e.size(); i++) {
        if (e[i].u == k && e[i].v != k0) {
            if (find_cycle(e, e[i].v, k, cycle)) return true;
        }
        if (e[i].v == k && e[i].u != k0) {
            if (find_cycle(e, e[i].u, k, cycle)) return true;
        }
    }
    cycle->erase(k);

    return false;
}

int solve(const vector<Edge>& e, int k, const set<int>& cycle)
{
    int sum = 0;

    vector<Edge>::const_iterator p = e.begin();
    while(k > 0) {
        if (p == e.end()) { return kInf; }
        if (!contains(cycle, p->u) || !contains(cycle, p->v)) {
            sum += p->cost; --k;
        }
        ++p;
    }
    return sum;
}

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<Edge> e(m);
    for (int i = 0; i < m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].cost;
        --e[i].u, --e[i].v;
    }
    sort(e.begin(), e.end());

    vector<int> g(n);
    set<int> cycle;
    for (int i = 0; i < n; i++) {
        g[i] = i;
    }
    for (int i = 0; i < m; i++) {
        int g1 = g[e[i].u], g2 = g[e[i].v];
        if (g1 == g2) {
            find_cycle(e, e[i].u, -1, &cycle);
        } else {
            replace(g.begin(), g.end(), max(g1, g2), min(g1, g2));
        }
    }

    sort(g.begin(), g.end());
    int k0 = unique(g.begin(), g.end()) - g.begin();

    int ans = solve(e, k - k0, cycle);
    int cut = -1;
    for (int i = 0; i < m; i++) {
        if (contains(cycle, e[i].u) && contains(cycle, e[i].v)) {
            int extra_cost = e[i].cost;
            e.erase(e.begin() + i);
            ans = min(ans, solve(e, k - k0, set<int>()) + extra_cost);
            break;
        }
    }
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result