题解
从图中删边,直到图中只剩(k)条边,计算权值之和即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#define gI gi
#define itn int
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
int n, m, k, tot, ans, sum, fa[1003];
struct OrzAncer
{
int x, y, l;
} a[10003];
int getf(int u)
{
if (fa[u] == u) return u;
return fa[u] = getf(fa[u]);
}
inline bool cmp(OrzAncer X, OrzAncer Y) {return X.l < Y.l;}
int main()
{
//File("P1195");
n = gi(), m = gi(), k = gi();
for (int i = 1; i <= m; i+=1)
{
a[i].x = gi(), a[i].y = gi(), a[i].l = gi();
}
for (int i = 1; i <= n; i+=1) fa[i] = i;
sort(a + 1, a + 1 + m, cmp);
tot = n;
bool fl = true;
for (int i = 1; i <= m; i+=1)
{
int u = getf(a[i].x), v = getf(a[i].y);
if (u != v)
{
fa[u] = v;
--tot;//删边
ans = ans + a[i].l;
if (tot == k) {fl = false; break;}//删完了
}
}
if (fl) puts("No Answer");
else printf("%d
", ans);
return 0;
}