CF875F Royal Questions解题报告

未分类

CF875F Royal Questions解题报告：

更好的阅读体验

题意

• $n$个王子，$m$个公主，每个公主有嫁妆$w_i$；
• 王子和公主都只能有一个伴侣，每个公主有两个喜欢的王子（只能挑选喜欢的王子作为伴侣）；
• 作为国王，你要选择王子的伴侣，达到收获的嫁妆最多。
• 数据范围：$2\leqslant n\leqslant 2\cdot 10^5,1\leqslant m\leqslant 2\cdot 10^5$。

分析

贪心+并查集妙题

考虑定义一条有向边$u\rightarrow v$的意义为$u$把公主让给了$v$，那么每个点一定入度为$1$，所有的边会形成一个外向基环树森林。

贪心地把公主按照嫁妆从大到小排序，每个公主看成一条无向边，那么可行的方案一定会形成一个基环树森林。

用并查集维护所有王子组成的基环树，用标记$flg$来记录一个并查集代表的集合为基环树还是树，然后考虑选择一条边的方法：

• 如果合并的两个点属于同一个并查集：
• • 如果这个并查集是一棵树，那么可以选，并标记为基环树；
• • 否则不选。
• 如果合并的两个点不属于一个并查集：
• • 如果合并两棵树，那么可以选，标记为树；
• • 如果合并一棵树，一棵基环树，那么可以选，标记为基环树；
• • 否则不选。

代码

#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=200005,maxm=200005; 
int n,m,e,ans;
int f[maxn],flg[maxn];
struct edge{
    int x,y,z;
}g[maxm];
inline int cmp(edge a,edge b){
    return a.z>b.z;
}
int find(int x){
    return f[x]==x? x:f[x]=find(f[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].z);
    sort(g+1,g+1+m,cmp);
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++){
        int x=find(g[i].x),y=find(g[i].y);
        if(x==y){
            if(flg[x]==0)
                flg[x]=1,ans+=g[i].z;
            continue;
        }
        if(flg[x]+flg[y]<=1){
            f[y]=x,flg[x]=flg[x]+flg[y];
            ans+=g[i].z;
        }
    }
    printf("%d\n",ans);
    return 0;
}