#include\x20 #include\x20 #include\x20 #include\x20

using\x20namespace\x20std;

struct\x20Edge\x20{ \x20\x20int\x20u, v, cost; };

vector parent; vector size;

int\x20find(int u) { \x20\x20if (parent[u] == u) { \x20\x20\x20\x20return u; \x20\x20} \x20\x20return parent[u] = find(parent[u]); }

void unite(int u, int v) { \x20\x20u = find(u); \x20\x20v = find(v); \x20\x20if (u == v) { \x20\x20\x20\x20return; \x20\x20} \x20\x20if (size[u] < size[v]) { \x20\x20\x20\x20swap(u, v); \x20\x20} \x20\x20parent[v] = u; \x20\x20size[u] += size[v]; }

bool same(int u, int v) { \x20\x20return find(u) == find(v); }

int kruskal(vector& edges, int n, int k) { \x20\x20int ans = 0; \x20\x20parent.resize(n); \x20\x20size.resize(n); \x20\x20for (int i = 0; i < n; i++) { \x20\x20\x20\x20parent[i] = i; \x20\x20\x20\x20size[i] = 1; \x20\x20} \x20\x20priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; \x20\x20for (int i = 0; i < edges.size(); i++) { \x20\x20\x20\x20pq.push({edges[i].cost, i}); \x20\x20} \x20\x20int count = 0; \x20\x20while (!pq.empty() && count < n - k) { \x20\x20\x20\x20int cost = pq.top().first; \x20\x20\x20\x20int idx = pq.top().second; \x20\x20\x20\x20pq.pop(); \x20\x20\x20\x20if (!same(edges[idx].u, edges[idx].v)) { \x20\x20\x20\x20\x20\x20unite(edges[idx].u, edges[idx].v); \x20\x20\x20\x20\x20\x20ans += cost; \x20\x20\x20\x20\x20\x20count++; \x20\x20\x20\x20} \x20\x20} \x20\x20if (count < n - k) { \x20\x20\x20\x20return -1; \x20\x20} \x20\x20return ans; }

int main() { \x20\x20int n, m, k; \x20\x20cin >> n >> m >> k; \x20\x20vector edges; \x20\x20for (int i = 0; i < m; i++) { \x20\x20\x20\x20int u, v, cost; \x20\x20\x20\x20cin >> u >> v >> cost; \x20\x20\x20\x20edges.push_back({u, v, cost}); \x20\x20} \x20\x20int ans = kruskal(edges, n, k); \x20\x20if (ans == -1) { \x20\x20\x20\x20cout << "No Answer" << endl; \x20\x20} else { \x20\x20\x20\x20cout << ans << endl; \x20\x20} \x20\x20return 0; }


原文地址: https://www.cveoy.top/t/topic/pDRS 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录