题目链接
题目大意
从原先给出的m条边中选出最多k条边，使得任意可到达两点之间的路径只有一条，最后要使整个图的权值和最大。
最小生成树 （懂的大佬请自行跳过）
我们先来看看什么是最小生成树。 最小生成树是一颗任意两个节点之间只有一条路径，并且整棵树的权值和最小的一颗树。
区别
我们这道题是求整个图的最大值，所以我们只要把它当作一棵最大生成树就好了，只需要修改最小生成树的排序方式就好了。
上代码！！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
#define pi acos(-1)
#define inf 0x3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define piii pair<pii, int>
#define uf(a, b, i) for (register int i = (a); i <= (b); ++i)
#define df(a, b, i) for (register int i = (a); i >= (b); --i)
using namespace std
;
inline int read() {
int x
= 0, f
= 1;
char ch
= getchar();
while(ch
< '0' || ch
> '9') {
if(ch
== '-') f
= -1;
ch
= getchar();
}
while(ch
>= '0' && ch
<= '9') {
x
= x
* 10 + ch
- '0';
ch
= getchar();
}
return x
* f
;
}
template<class T>
inline void print(T x
) {
if(x
> 9) print(x
/10);
putchar(x
%10 + '0');
}
template<class T>
T
Max(T a
, T b
) {
return a
> b
? a
: b
;
}
template<class T>
T
Min(T a
, T b
) {
return a
< b
? a
: b
;
}
const ll mod
= 1e9 + 7;
struct edg
{
int u
, v
, w
;
bool operator < (const edg
&e1
) {
return w
> e1
.w
;
}
} e
[100005];
int n
, m
, k
;
ll ans
;
int f
[100005];
int find(int x
) {
return f
[x
] == x
? x
: (f
[x
] = find(f
[x
]));
}
void scan() {
n
= read(); m
= read(); k
= read();
uf(1, m
, i
) {
e
[i
].u
= read(); e
[i
].v
= read(); e
[i
].w
= read();
}
}
void work() {
sort(e
+1, e
+m
+1);
uf(1, n
, i
) f
[i
] = i
;
uf(1, m
, i
) {
int fu
= find(e
[i
].u
), fv
= find(e
[i
].v
);
if (fu
!= fv
) {
f
[fu
] = fv
;
ans
+= e
[i
].w
;
--k
;
}
if (!k
) break;
}
print(ans
);
putchar('\n');
}
int main() {
scan();
work();
return 0;
}
