传送门
\(a[i]\) 和 \(b[i]\) 之间连一条 \(w[i]\) 的边，相当于把公主当作限制条件。
考虑选当前这条边是否合法：
1.若选了当前这条边后变成了一棵树，那即为 \(x\) 个点和 \(x-1\) 个边，可以任意舍去一个点（因为可以有王子不结婚），所以一定合法。
2.若选了当前这条边后，变成了一棵基环树，即为 \(x\) 个点和 \(x\) 条边，那显然一定合法。
重点在于判选了这条边后是否是一个基环树。考虑仍使用 \(kruskal\) 的方法，排序后依次考虑。若当前的边的两端 \(a，b\) 在同一个树内，那连上这条边会让他变成一个基环树，否则的话会变成一棵树。设 \(vis[i]\) 表示以 \(i\) 为根的集合是树/基环树。 \(vis[i] = 0\) 表示树，反之基环树。
不难得知一棵树和一棵树合并一定会变成一棵树，一棵树和一棵基环树合并会变成一棵基环树。然后在加边的时候按照这个进行判断即可，细节看代码。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
struct node {
int a, b, k;
}g[N];
bool cmp(node x, node y) {
return x.k > y.k;
}
int fa[N], vis[N];
int findfa(int x) {
if(fa[x] == x) return x;
return fa[x] = findfa(fa[x]);
}
int main () {
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) fa[i] = i, vis[i] = 1;
for(int i = 1; i <= m; i ++) {
cin >> g[i].a >> g[i].b >> g[i].k;
}
sort(g + 1, g + m + 1, cmp);
int cnt = 0, ans = 0;
for(int i = 1; i <= m; i ++) {
int fx = findfa(g[i].a), fy = findfa(g[i].b);
if(fx != fy) {
if(vis[fx] == 1 || vis[fy] == 1) {
fa[fy] = fx;
if(vis[fx] == 0 || vis[fy] == 0) vis[fx] = 0;
else vis[fx] = 1;
ans += g[i].k;
cnt ++;
}
}
else {
if(vis[fx]) {
ans += g[i].k;
vis[fx] = 0;
cnt ++;
}
}
if(cnt == n) break;
}
cout << ans << endl;
}