首先题目显然可以建模为一个二分图的最大权匹配问题。我们将王子放在左侧，公主放在右侧。根据贪心的思想，将公主按价值从大到小排序，每次搜索交错树；若找到未匹配节点，直接增广，否则丢弃该节点。这样我们就得到了一个 \(O(m(m+n))\) 的算法。但这个复杂度显然不够优秀，我们要寻找加速它的方法。
首先直接给出算法如下：初始化所有 \(n+m\) 个节点的并查集。同样将公主按价值从大到小排序。对她的两个相邻王子节点，若其并查集中所在连通块的大小为奇数，则可以取该公主节点，并同时将公主节点与相邻两节点在并查集中连通。否则丢弃该公主节点。
该算法的正确性依赖于以下结论：在我们的连接规则下，若一个邻王子节点所在连通块的大小为奇数，意味着交错树中存在未匹配节点。下面简单证明这个结论。
首先，根据我们的连接方式，显然交错树的对应部分包含于对应连通块中。注意到由于公主节点的度为 2 ，交错树这样的一个部分一定为链或者环；且为链时，存在未匹配节点；为环时不存在。若连通块中不存在除交错树外的节点，显然连通块的奇偶性决定了为链或者环的性质。而连通块中除交错树外的节点一定是两两匹配的节点，所以个数为偶，不影响上面的性质。
通过代码（C++）：
#include <bits/stdc++.h>
using namespace std;
// 并查集代码
class UnionFindSet {
vector<int> F;
vector<int> rank;
int n;
public:
UnionFindSet(int _n) {
n = _n;
F.resize(n);
rank.resize(n, 1);
for (int i = 0; i < n; i++) {
F[i] = i;
}
}
int size(int x) { return rank[find(x)]; }
int find(int x) {
return x == F[x] ? x : F[x] = find(F[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy)
return;
if (rank[fx] < rank[fy])
swap(fx, fy);
F[fy] = fx;
rank[fx] += rank[fy];
}
};
using i64 = int64_t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> v;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
a--, b--;
v.push_back({w, i, a, b});
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
auto ufs = UnionFindSet(n + m);
i64 ans = 0;
for (auto v : v) {
int w = v[0], i = v[1], a = v[2], b = v[3];
if (ufs.size(a) % 2 == 1 || ufs.size(b) % 2 == 1) {
ans += w;
ufs.merge(i + n, a);
ufs.merge(i + n, b);
}
}
cout << ans << endl;
}