题目链接

Royal Questions - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析

每个公主会选择两个王子，考虑将每个公主所选择的两个王子连边，边权为该公主的嫁妆

选择该边即为选择该公主

那么结果图是什么呢？

由于每个王子最多只能选择一个公主即每个点最多有1个出边（也可能没有出边）

那么最多有 n 条边

类似 kruskal 将边权由大到小排序，贪心选择即可

与最小生成树算法唯一不同的是每个连通块里可以有一个环

用f数组记录即可

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N=200005;
 5 
 6 struct EDGE{
 7 int x,y,w;
 8 }e[N];
 9 int tot=0;
10 bool cmp(EDGE a,EDGE b){return a.w>b.w;}
11 
12 int fa[N];
13 bool f[N];//每个连通块是否有环
14 int find(int x){
15 if(fa[x]==x) return x;
16 else return fa[x]=find(fa[x]);
17 }
18 
19 int main(){
20 int n,m,ans=0;
21 scanf("%d %d", &n, &m);
22 for(int i=1;i<=m;i++){
23 int x,y,z;
24 scanf("%d %d %d", &x, &y, &z);
25 e[++tot]={x,y,z};
26 }
27 sort(e+1,e+m+1,cmp);
28 for(int i=1;i<=n;i++) fa[i]=i;
29 for(int i=1;i<=m;i++){
30 int x=e[i].x,y=e[i].y,w=e[i].w;
31 int p=find(x),q=find(y);
32 if(p==q){
33 if(!f[p]) ans+=w,f[p]=1;//每个连通块最多有一个环
34 continue;
35 }
36 if(f[q]&&f[p]) continue;//若两个连通块都有环则continue
37 fa[p]=q;
38 f[q]|=f[p];//更新是否有环
39 ans+=w;
40 }
41 printf("%d\n", ans);
42 return 0;
43 }

与Card Collector - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)类似